Interval Overlap Counting Greedy

Description

Trains arrive and depart; how many platforms does the station need so no train waits? Meetings start and end; how many rooms? Both ask for the largest number of intervals active at the same moment - and checking every pair of intervals, or every moment, is far more work than needed.

This skill covers the event sweep that answers this in O(n log n): sort the starts and ends, walk through them, and keep the running count and its maximum. It also covers the tie rule each problem sets, weighted events with a difference array, and why the peak is always enough capacity.

We'll go from simple to more technical:

1. The pattern: sort arrivals and departures separately and sweep, tracking the running count.
2. A second flavor: weighted events (Car Pooling) with a difference array.
3. Where peak concurrency shows up (requests, connections, licenses, rooms, vehicles).
4. What breaks it: the tie rule, pairwise checks, midnight, off-by-one in difference arrays.

The approach

int minPlatforms(int[] arrival, int[] departure) {
    int[] arr = arrival.clone(), dep = departure.clone();
    Arrays.sort(arr);
    Arrays.sort(dep);                                // sorted separately: only counts matter
    int active = 0, best = 0, j = 0;
    for (int i = 0; i < arr.length; i++) {
        while (j < dep.length && dep[j] < arr[i]) {  // trains gone strictly before this arrival
            active--;
            j++;
        }
        active++;
        best = Math.max(best, active);
    }
    return best;
}

def min_platforms(arrival: list[int], departure: list[int]) -> int:
    arr, dep = sorted(arrival), sorted(departure)   # sorted separately: only counts matter
    active = best = j = 0
    for a in arr:
        while j < len(dep) and dep[j] < a:          # trains gone strictly before this arrival
            active -= 1
            j += 1
        active += 1
        best = max(best, active)
    return best

The count at any moment is "arrivals so far minus departures so far", so which train an event belongs to doesn't matter - arrivals and departures can be sorted independently. The tie rule is part of the problem: here a train holds its platform through its departure minute, so a train arriving at 200 can't use the platform of one departing at 200 (only departures strictly before an arrival free a platform). Arrivals [100, 200] and departures [200, 300] need 2 platforms under this rule, 1 if the platform frees instantly.

The answer is also a lower bound that's always achievable: at the busiest moment every active train needs its own platform, and assigning each arriving train any free platform never needs more than that.

A second flavor: events that carry weights

Car Pooling: trips carry passengers from from to to, and the car must never hold more than capacity. Passengers leave at to before anyone boards there. With stops in a small range, a difference array records the changes and a prefix sum replays them:

boolean carPooling(int[][] trips, int capacity) {    // each trip is [passengers, from, to]
    int[] change = new int[1001];
    for (int[] t : trips) {
        change[t[1]] += t[0];                        // they board at from
        change[t[2]] -= t[0];                        // and are out of the car at to
    }
    int inCar = 0;
    for (int c : change) {
        inCar += c;
        if (inCar > capacity) return false;
    }
    return true;
}

def car_pooling(trips: list[list[int]], capacity: int) -> bool:   # each trip is [passengers, from, to]
    change = [0] * 1001
    for passengers, start, end in trips:
        change[start] += passengers                 # they board at from
        change[end] -= passengers                   # and are out of the car at to
    in_car = 0
    for c in change:
        in_car += c
        if in_car > capacity:
            return False
    return True

Applying the drop-off at to itself (not to + 1) encodes "off before on": trips [2, 1, 5] and [3, 5, 7] fit in a car of 3. With large or real-valued coordinates, sort the events instead - by position, with drop-offs before pick-ups at equal positions.

Where you'll see it

Peak concurrent requests from access logs (sort start and end timestamps and sweep), the number of database connections or licenses needed at peak, meeting rooms for a day's calendar, and capacity checks for rides or shared vehicles are all event sweeps.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why can arrivals and departures be sorted separately?

2. Arrivals [100, 200], departures [200, 300]: 1 platform or 2?

3. In Car Pooling, why subtract the passengers at to and not at to + 1?

Key takeaways

• Peak overlap: sort starts and ends separately, sweep, track the running maximum.
• The tie rule (does an end at t free room for a start at t?) comes from the problem - encode it deliberately.
• Minimum platforms or rooms equals the maximum overlap.
• Weighted events: a difference array plus prefix sums, or sorted events with the right tie order.