Interval problems

Intervals and overlap

An interval [start, end] covers every time from start to end. Two intervals a and b overlap when a.start ≤ b.end and b.start ≤ a.end. The tricky part is the edges: do [1, 4] and [4, 5] overlap? For merging free time slots we usually say yes (they touch, so they join into [1, 5]); for meetings that may run back to back we usually say no. Always ask, and write the comparison (< or ≤) to match.

Without sorting, checking every pair is O(n²). After sorting by start time, any interval can only overlap the ones near it in the list, so one pass is enough: O(n log n) for the sort plus O(n).

Merge overlapping intervals

Sort by start. Walk through; if the current interval starts at or before the end of the last merged one, extend that end (take the max, because the current one may be fully inside). Otherwise start a new merged interval.

def merge(intervals):
    merged = []
    for start, end in sorted(intervals):
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

print(merge([[8, 10], [1, 3], [2, 6], [15, 18], [6, 7]]))   # Output: [[1, 7], [8, 10], [15, 18]]

Insert an interval into a sorted list

When the list is already sorted and non-overlapping, inserting a new interval does not need a full sort. Copy every interval that ends before the new one starts; then absorb every interval that starts before the new one ends, widening the new interval; then copy the rest. That is O(n).

def insert(intervals, new):
    result, i, n = [], 0, len(intervals)
    start, end = new
    while i < n and intervals[i][1] < start:      # completely before
        result.append(intervals[i])
        i += 1
    while i < n and intervals[i][0] <= end:       # overlapping: absorb
        start = min(start, intervals[i][0])
        end = max(end, intervals[i][1])
        i += 1
    result.append([start, end])
    result.extend(intervals[i:])                   # completely after
    return result

print(insert([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]))   # Output: [[1, 2], [3, 10], [12, 16]]

Minimum meeting rooms

How many rooms are needed so every meeting gets one? Sort meetings by start. Keep a min-heap of the END times of meetings currently using a room. For each meeting, if the earliest-ending room is already free (its end ≤ this start), reuse it with heapreplace; otherwise open a new room. The heap size at the end is the answer: O(n log n). Another way sorts all starts and all ends separately and walks them with two pointers, counting how many meetings are running at once.

import heapq

def min_rooms(meetings):
    ends = []
    for start, end in sorted(meetings):
        if ends and ends[0] <= start:
            heapq.heapreplace(ends, end)     # reuse the room that frees first
        else:
            heapq.heappush(ends, end)        # open a new room
    return len(ends)

print(min_rooms([(0, 30), (5, 10), (15, 20)]), min_rooms([(1, 5), (5, 8)]))   # Output: 2 1

Railway platforms: the classic Indian question

A station has the arrival and departure times of every train for one day, written as numbers such as 900 for 9:00 and 1120 for 11:20 (comparing them as numbers works within one day). How many platforms are needed so no train waits? This is the meeting-rooms question again. Sort the arrivals and the departures SEPARATELY. Walk both lists: when the next event is an arrival, one more train is on a platform; when it is a departure, one fewer. The largest count seen is the answer.

The edge rule matters. The usual version of this question says that if a train arrives at exactly the time another departs, the arriving train needs a NEW platform (the leaving train is still standing there). So an arrival is processed before a departure at the same time: compare with arrival <= departure.

def min_platforms(arr, dep):
    arr, dep = sorted(arr), sorted(dep)
    i = j = 0
    on_platform = best = 0
    while i < len(arr):
        if arr[i] <= dep[j]:          # equal time: the arrival needs its own platform
            on_platform += 1
            best = max(best, on_platform)
            i += 1
        else:
            on_platform -= 1
            j += 1
    return best

print(min_platforms([900, 940, 950, 1100, 1500, 1800], [910, 1200, 1120, 1130, 1900, 2000]))   # Output: 3

Fewest intervals to remove

To make the rest non-overlapping with the fewest removals, keep as many intervals as possible: that is activity selection again (Topic 3). Sort by END, keep each interval that starts at or after the last kept end, and count the others as removed. Touching intervals such as [1, 2] and [2, 3] do not overlap here.

Common mistakes

• Forgetting to sort first, or sorting by the wrong key. Merge: by start. Keep the most: by end.
• Setting merged[-1][1] = end instead of max(...). An interval inside another, like [1, 10] then [2, 3], would shrink it.
• Getting the touching rule wrong. Fix: ask, then use < or <= on purpose, and test with a pair that touches.
• In JavaScript, sorting with arr.sort() and no compare function. It sorts as strings, so 10 comes before 9. Fix: arr.sort((a, b) => a[0] - b[0]).
• In the platform problem, pairing each sorted arrival with the sorted departure at the same index as if they were the same train. Fix: the two lists are just events; only the counts matter.