# Intervals — Part 2: Interview Problems

Six problems covering the three strategies: merge by start, greedy by end, and counting overlaps with a heap or sweep line.

## 1. Merge Intervals (LeetCode 56)

**🟠 Medium.** Merge all overlapping intervals and return the non-overlapping result.

```text
[[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]
```

**Approach.** Sort by start. Walk the intervals: if the current one starts before (or at) the end of the last merged interval, extend that interval's end; otherwise start a new one.

**Complexity.** O(n log n) time for sorting, O(n) for the output.

```typescript
function merge(intervals: number[][]): number[][] {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const merged: number[][] = [];
  for (const [s, e] of sorted) {
    const last = merged[merged.length - 1];
    if (last && s <= last[1]) last[1] = Math.max(last[1], e);
    else merged.push([s, e]);
  }
  return merged;
}
```

```python
def merge(intervals):
    intervals = sorted(intervals, key=lambda iv: iv[0])
    merged = []
    for s, e in intervals:
        if merged and s <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], e)
        else:
            merged.append([s, e])
    return merged
```

## 2. Insert Interval (LeetCode 57)

**🟠 Medium.** `intervals` is sorted and non-overlapping. Insert `newInterval`, merging where needed.

```text
[[1,2],[3,5],[6,7],[8,10],[12,16]] + [4,8] → [[1,2],[3,10],[12,16]]
```

**Approach.** Three phases in one pass: copy intervals that end before the new one starts; merge every interval that overlaps it (expand the new interval's start/end); copy the rest. No sort needed: O(n).

**Complexity.** O(n) time.

```typescript
function insert(intervals: number[][], newInterval: number[]): number[][] {
  const res: number[][] = [];
  let i = 0;
  let [s, e] = newInterval;
  while (i < intervals.length && intervals[i][1] < s) res.push(intervals[i++]);
  while (i < intervals.length && intervals[i][0] <= e) {
    s = Math.min(s, intervals[i][0]);
    e = Math.max(e, intervals[i][1]);
    i++;
  }
  res.push([s, e]);
  while (i < intervals.length) res.push(intervals[i++]);
  return res;
}
```

```python
def insert(intervals, new):
    res, i, n = [], 0, len(intervals)
    s, e = new
    while i < n and intervals[i][1] < s:          # entirely before
        res.append(intervals[i]); i += 1
    while i < n and intervals[i][0] <= e:         # overlapping: absorb
        s, e = min(s, intervals[i][0]), max(e, intervals[i][1]); i += 1
    res.append([s, e])
    res.extend(intervals[i:])                     # entirely after
    return res
```

## 3. Non-overlapping Intervals (LeetCode 435)

**🟠 Medium.** Return the minimum number of intervals to remove so that the rest don't overlap (touching endpoints are fine).

```text
[[1,2],[2,3],[3,4],[1,3]] → 1   (remove [1,3])
```

**Approach.** Equivalent to keeping the maximum number of non-overlapping intervals. Sort by **end**; keep an interval if it starts at or after the end of the last kept one, otherwise remove it. Earliest-finishing first leaves the most room.

**Complexity.** O(n log n) time, O(1) extra space.

```typescript
function eraseOverlapIntervals(intervals: number[][]): number {
  const sorted = [...intervals].sort((a, b) => a[1] - b[1]);
  let removed = 0, lastEnd = -Infinity;
  for (const [s, e] of sorted) {
    if (s >= lastEnd) lastEnd = e; else removed++;
  }
  return removed;
}
```

```python
def erase_overlap_intervals(intervals):
    intervals = sorted(intervals, key=lambda iv: iv[1])
    removed, last_end = 0, float("-inf")
    for s, e in intervals:
        if s >= last_end:
            last_end = e            # keep it
        else:
            removed += 1            # overlaps the kept one → remove
    return removed
```

## 4. Meeting Rooms (LeetCode 252)

**🟢 Easy.** Can one person attend all meetings? (Intervals are half-open: a meeting ending at 10 doesn't conflict with one starting at 10.)

```text
[[0,30],[5,10],[15,20]] → false
```

**Approach.** Sort by start; any meeting that starts before the previous one ends is a conflict.

**Complexity.** O(n log n) time.

```typescript
function canAttendMeetings(intervals: number[][]): boolean {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  for (let i = 1; i < sorted.length; i++) if (sorted[i][0] < sorted[i - 1][1]) return false;
  return true;
}
```

```python
def can_attend_meetings(intervals):
    intervals = sorted(intervals)
    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i - 1][1]:
            return False
    return True
```

## 5. Meeting Rooms II (LeetCode 253)

**🟠 Medium.** Return the minimum number of conference rooms needed for all meetings (half-open intervals).

```text
[[0,30],[5,10],[15,20]] → 2
```

**Approach.** Sort meetings by start and keep a **min-heap of end times** of rooms in use. For each meeting, if the earliest-ending room is free by its start, reuse it (pop); then push this meeting's end. The heap size is the number of rooms. (Equivalent: sweep over +1/−1 events and take the peak.)

**Complexity.** O(n log n) time, O(n) space.

```typescript
function minMeetingRooms(intervals: number[][]): number {
  // sweep line: starts and ends sorted separately
  const starts = intervals.map((i) => i[0]).sort((a, b) => a - b);
  const ends = intervals.map((i) => i[1]).sort((a, b) => a - b);
  let rooms = 0, best = 0, j = 0;
  for (let i = 0; i < starts.length; i++) {
    while (j < ends.length && ends[j] <= starts[i]) { rooms--; j++; }   // free rooms first
    rooms++;
    best = Math.max(best, rooms);
  }
  return best;
}
```

```python
import heapq

def min_meeting_rooms(intervals):
    ends = []                                   # end times of rooms in use
    for s, e in sorted(intervals):
        if ends and ends[0] <= s:
            heapq.heappop(ends)                 # that room is free again
        heapq.heappush(ends, e)
    return len(ends)
```

## 6. Minimum Number of Arrows to Burst Balloons (LeetCode 452)

**🟠 Medium.** Balloons span `[xstart, xend]` (closed). An arrow at x bursts every balloon containing x. Return the minimum number of arrows.

```text
[[10,16],[2,8],[1,6],[7,12]] → 2   (arrows at 6 and 12)
```

**Approach.** Sort by end. Shoot the first arrow at the first balloon's end; it bursts every balloon starting at or before that point. When a balloon starts after the current arrow, shoot a new arrow at its end.

**Complexity.** O(n log n) time.

```typescript
function findMinArrowShots(points: number[][]): number {
  const sorted = [...points].sort((a, b) => a[1] - b[1]);
  let arrows = 0, arrowX = -Infinity;
  for (const [s, e] of sorted) {
    if (s > arrowX) { arrows++; arrowX = e; }
  }
  return arrows;
}
```

```python
def find_min_arrow_shots(points):
    points = sorted(points, key=lambda p: p[1])
    arrows, arrow_x = 0, float("-inf")
    for s, e in points:
        if s > arrow_x:              # not hit by the current arrow
            arrows += 1
            arrow_x = e
    return arrows
```