# Interval Problems — DSA Interview Patterns

Source: https://www.skillbyai.com/en/dsa-interview-patterns/x-intervals

> Sort by start, then sweep.

## 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.

```python
# 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.

**Quiz:** What is the usual first step in interval problems?

- [ ] Reverse the list
- [x] Sort intervals by start time
- [ ] Convert to a graph
- [ ] Use binary search immediately

*Answer:* Sort intervals by start time. Order makes a single sweep possible.