Interval Problems

Merge and count overlaps

Most interval problems start by sorting by start time. Merging overlapping intervals extends the last merged interval when the next one starts before it ends. Counting meeting rooms keeps a min-heap of end times: a room is reused when the earliest end is not after the next start. Clarify whether touching intervals ([1,4] and [4,5]) overlap.

Merging intervals and counting rooms, run

I ran this with Python 3.12.3 (standard library only). Overlapping [1,3] and [2,6] merge; touching intervals merge because the code uses <=; three meetings need 2 rooms and two separate meetings need 1.

# Intervals: merge overlaps and count rooms needed
import heapq

def merge(intervals):
    out = []
    for s, e in sorted(intervals):
        if out and s <= out[-1][1]:
            out[-1][1] = max(out[-1][1], e)
        else:
            out.append([s, e])
    return out

def min_rooms(meetings):
    ends = []                             # min-heap of end times in use
    for s, e in sorted(meetings):
        if ends and ends[0] <= s:
            heapq.heappop(ends)           # reuse a room that is free
        heapq.heappush(ends, e)
    return len(ends)

print(merge([[1, 3], [2, 6], [8, 10], [15, 18]]))
print(merge([[1, 4], [4, 5]]))
print(min_rooms([(0, 30), (5, 10), (15, 20)]), min_rooms([(7, 10), (2, 4)]))

Output:

[[1, 6], [8, 10], [15, 18]]
[[1, 5]]
2 1

Ask about touching endpoints

Whether [1,4] and [4,5] overlap changes < to <=; ask instead of guessing.

त्वरित जाँच: What is the usual first step in interval problems?

• Reverse the list
• Sort intervals by start time
• Convert to a graph
• Use binary search immediately