091. Maximum Concurrent Intervals

Why this mechanism works

Replace each duration by a +1 start event and a -1 end event. At equal timestamps, process endings before starts so the sweep respects half-open membership. The active count after an event is a running balance; its maximum is the requested concurrency.

State and boundaries

active counts intervals covering the current sweep position after the processed boundary events. peak is the maximum observed active count.

Protocol

1. Create two events for each nonempty interval.
2. Sort by time then delta, putting -1 before +1.
3. Apply each delta.
4. Update peak.
5. Return peak.

Visualization

[1,3) [3,5)
time 3: end -1, then start +1
active never exceeds 1

Python implementation

def maximum_concurrency(intervals):
    events = []
    for start, end in intervals:
        if start < end:
            events.extend(((start, 1), (end, -1)))
    active = peak = 0
    for time, delta in sorted(events):
        active += delta
        peak = max(peak, active)
    return peak

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 maximum_concurrency: events = []
intervals=[(0, 30), (5, 10), (15, 20)]; events=[]

L3 maximum_concurrency: for start, end in intervals:
intervals=[(0, 30), (5, 10), (15, 20)]; events=[]; start=0; end=30

L5 maximum_concurrency: events.extend(((start, 1), (end, -1)))
intervals=[(0, 30), (5, 10), (15, 20)]; events=[(0, 1), (30, -1)]; start=0; end=30

L3 maximum_concurrency: for start, end in intervals:
intervals=[(0, 30), (5, 10), (15, 20)]; events=[(0, 1), (30, -1)]; start=5; end=10

L5 maximum_concurrency: events.extend(((start, 1), (end, -1)))
intervals=[(0, 30), (5, 10), (15, 20)]; events=[(0, 1), (30, -1), (5, 1), (10, -1)]; start=5; end=10

L3 maximum_concurrency: for start, end in intervals:
intervals=[(0, 30), (5, 10), (15, 20)]; events=[(0, 1), (30, -1), (5, 1), (10, -1)]; start=15; end=20

L5 maximum_concurrency: events.extend(((start, 1), (end, -1)))
intervals=[(0, 30), (5, 10), (15, 20)]; events=[(0, 1), (30, -1), (5, 1), (10, -1), (15, 1), (20, -1)]; start=15; end=20

L6 maximum_concurrency: active = peak = 0
intervals=[(0, 30), (5, 10), (15, 20)]; events=[(0, 1), (30, -1), (5, 1), (10, -1), (15, 1), (20, -1)]; start=15; end=20; active=0; peak=0

... 10 intermediate state changes omitted ...

L7 maximum_concurrency: for time, delta in sorted(events):
intervals=[(0, 30), (5, 10), (15, 20)]; events=[(0, 1), (30, -1), (5, 1), (10, -1), (15, 1), (20, -1)]; start=15; end=20; active=2; peak=2; time=20; delta=-1

L8 maximum_concurrency: active += delta
intervals=[(0, 30), (5, 10), (15, 20)]; events=[(0, 1), (30, -1), (5, 1), (10, -1), (15, 1), (20, -1)]; start=15; end=20; active=1; peak=2; time=20; delta=-1

L7 maximum_concurrency: for time, delta in sorted(events):
intervals=[(0, 30), (5, 10), (15, 20)]; events=[(0, 1), (30, -1), (5, 1), (10, -1), (15, 1), (20, -1)]; start=15; end=20; active=1; peak=2; time=30; delta=-1

L8 maximum_concurrency: active += delta
intervals=[(0, 30), (5, 10), (15, 20)]; events=[(0, 1), (30, -1), (5, 1), (10, -1), (15, 1), (20, -1)]; start=15; end=20; active=0; peak=2; time=30; delta=-1

L2 maximum_concurrency: events = []
intervals=[(1, 3), (3, 5)]; events=[]

L3 maximum_concurrency: for start, end in intervals:
intervals=[(1, 3), (3, 5)]; events=[]; start=1; end=3

L5 maximum_concurrency: events.extend(((start, 1), (end, -1)))
intervals=[(1, 3), (3, 5)]; events=[(1, 1), (3, -1)]; start=1; end=3

L3 maximum_concurrency: for start, end in intervals:
intervals=[(1, 3), (3, 5)]; events=[(1, 1), (3, -1)]; start=3; end=5

L5 maximum_concurrency: events.extend(((start, 1), (end, -1)))
intervals=[(1, 3), (3, 5)]; events=[(1, 1), (3, -1), (3, 1), (5, -1)]; start=3; end=5

L6 maximum_concurrency: active = peak = 0
intervals=[(1, 3), (3, 5)]; events=[(1, 1), (3, -1), (3, 1), (5, -1)]; start=3; end=5; active=0; peak=0

L7 maximum_concurrency: for time, delta in sorted(events):
intervals=[(1, 3), (3, 5)]; events=[(1, 1), (3, -1), (3, 1), (5, -1)]; start=3; end=5; active=0; peak=0; time=1; delta=1

L8 maximum_concurrency: active += delta
intervals=[(1, 3), (3, 5)]; events=[(1, 1), (3, -1), (3, 1), (5, -1)]; start=3; end=5; active=1; peak=0; time=1; delta=1

... 3 intermediate state changes omitted ...

L7 maximum_concurrency: for time, delta in sorted(events):
intervals=[(1, 3), (3, 5)]; events=[(1, 1), (3, -1), (3, 1), (5, -1)]; start=3; end=5; active=0; peak=1; time=3; delta=1

L8 maximum_concurrency: active += delta
intervals=[(1, 3), (3, 5)]; events=[(1, 1), (3, -1), (3, 1), (5, -1)]; start=3; end=5; active=1; peak=1; time=3; delta=1

L7 maximum_concurrency: for time, delta in sorted(events):
intervals=[(1, 3), (3, 5)]; events=[(1, 1), (3, -1), (3, 1), (5, -1)]; start=3; end=5; active=1; peak=1; time=5; delta=-1

L8 maximum_concurrency: active += delta
intervals=[(1, 3), (3, 5)]; events=[(1, 1), (3, -1), (3, 1), (5, -1)]; start=3; end=5; active=0; peak=1; time=5; delta=-1

Why the solution is correct

A start adds an interval exactly where it begins to be included; an end removes it exactly where inclusion stops. End-before-start ordering excludes endpoint-only contact. Between boundaries the count is unchanged, so checking event states finds its maximum.

Time and space

O(n log n) time and O(n) event space.

Common mistakes

Start-before-end ordering invents overlap at shared endpoints. Zero-length intervals must not create spurious start and end events.

Reasoning card

Transfer exercise

Return the time segments on which peak concurrency occurs, grouping all events at each timestamp before emitting a segment.