30. Min Agents for Overlap

Problem

Human agents pick up live conversations that Fin escalates during a shift. Given each escalated conversation's (start, end) time on the shift's timeline, compute the minimum number of human agents needed working simultaneously to handle every escalation, without any agent working two conversations at once.

Source: src/30_min_agents_for_overlap.py

def min_agents_needed(intervals: list[tuple[int, int]]) -> int: ...

min_agents_needed([(0, 30), (5, 10), (15, 20)])
# -> 2   ((5,10) and (15,20) both overlap (0,30), but not each other,
#          so at most 2 conversations are ever live at once)

min_agents_needed([(1, 5), (5, 10)])
# -> 1   (back-to-back, not overlapping -- one agent can handle both)

Step-by-Step Approach

1. If intervals is empty, return 0 immediately.
2. Split the intervals into two separate sorted lists: starts, all start times sorted ascending, and ends, all end times sorted ascending. Note these lists are no longer paired by original interval — that's fine, only the sorted order matters.
3. Initialize agents = 0 (agents currently busy), max_agents = 0 (the running maximum, which is the answer), and two pointers s_ptr, e_ptr both starting at 0.
4. Sweep forward while s_ptr < n (there are still starts to process). At each step, compare the next unprocessed start time against the next unprocessed end time.
5. If starts[s_ptr] < ends[e_ptr], a new conversation begins before the earliest currently-busy agent frees up: increment agents, update max_agents if this is a new high, and advance s_ptr.
6. Otherwise, the earliest busy agent frees up at or before the next start: decrement agents and advance e_ptr, without consuming a start.
7. When the sweep finishes, max_agents is the peak number of simultaneously overlapping conversations — the minimum number of agents needed.

The key insight is that you don't need to track which interval belongs to which agent — only how many are open at once — so merging all starts and ends into two sorted streams and sweeping them together (like merging two sorted lists) finds the peak concurrency in O(n log n) instead of checking every pair of intervals for overlap.

Reference solution

def min_agents_needed(intervals: list[tuple[int, int]]) -> int:
    # sort starts and ends separately, two-pointer sweep, O(n log n) time, O(n) space
    if not intervals:
        return 0
    # separate sorted arrays, pairing discarded
    starts = sorted(start for start, _ in intervals)
    ends = sorted(end for _, end in intervals)
    agents = 0
    max_agents = 0
    s_ptr = e_ptr = 0
    n = len(intervals)
    while s_ptr < n:
        # strict <: same-time end frees agent first
        if starts[s_ptr] < ends[e_ptr]:
            agents += 1
            # track running peak
            max_agents = max(max_agents, agents)
            s_ptr += 1
        else:
            # earliest busy agent frees up
            agents -= 1
            e_ptr += 1
    return max_agents

Key Functions & Tricks

• sorted(start for start, _ in intervals) — builds two separate sorted arrays, discarding the original pairing.
• Two-pointer sweep — walks starts/ends independently, like a merge-sort merge step.
• max_agents = max(max_agents, agents) — tracks the running peak on start events only.
• starts[s_ptr] < ends[e_ptr] — strict < so a same-time end frees an agent before a new start needs one.

How to Recognize This Pattern