# Interval and Greedy Interview Patterns: Meeting Rooms, Job Scheduling, and Activity Selection

Source: https://www.techinterview.org/post/3233460897/interval-greedy-interview-patterns/
Updated: 2026-04-16 · techinterview.org

## Why Greedy and Interval Problems

Greedy algorithms appear frequently in FAANG interviews because they test whether you can identify when a locally optimal choice leads to a globally optimal solution. Interval problems — merging, scheduling, covering — are the most common greedy category. Master the patterns and you can solve a wide family of problems by recognizing the underlying structure.

## Pattern 1: Merge Intervals

Given a list of intervals, merge all overlapping intervals. Sort by start time. Iterate: if the current interval overlaps the last merged interval (current.start <= merged.end), merge by extending the end. Otherwise, add the current interval as a new entry.


```
def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

# LeetCode 56: Merge Intervals
# LeetCode 57: Insert Interval (insert + merge)
# LeetCode 986: Interval List Intersections (two-pointer merge)
```


Time: O(N log N) for sorting, O(N) for merging. The key insight: after sorting by start, intervals can only overlap with the most recently merged interval — no need to look backward.

## Pattern 2: Meeting Rooms — Minimum Rooms Required

Given meeting time intervals, find the minimum number of conference rooms required. Classic greedy approach: sort meetings by start time. Use a min-heap storing end times of ongoing meetings. For each meeting: if the earliest-ending meeting ends before this one starts (heap.top <= current.start), reuse that room (pop and push new end time). Otherwise, add a new room (push to heap). The heap size at the end is the minimum rooms needed.


```
import heapq

def min_meeting_rooms(intervals):
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[0])
    heap = []  # end times of ongoing meetings
    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heapreplace(heap, end)  # reuse room
        else:
            heapq.heappush(heap, end)    # new room
    return len(heap)

# LeetCode 253: Meeting Rooms II
# Variant: LeetCode 1094 (Car Pooling) — same pattern with capacity
```


Alternative: chronological events scan. Create events: (start, +1) and (end, -1). Sort all events. Scan and track running sum; the maximum is the answer. This handles ties correctly (sort end before start if same time).

## Pattern 3: Activity Selection / Maximum Non-Overlapping Intervals

Given intervals, select the maximum number of non-overlapping intervals. Greedy choice: always select the interval that ends earliest. Sort by end time. Greedily select an interval if it starts after (or at) the last selected interval's end.


```
def erase_overlap_intervals(intervals):
    # Returns minimum number of intervals to REMOVE
    # Equivalently: N - max non-overlapping
    intervals.sort(key=lambda x: x[1])  # sort by end
    count = 0
    last_end = float('-inf')
    for start, end in intervals:
        if start >= last_end:
            count += 1  # select this interval
            last_end = end
    return len(intervals) - count

# LeetCode 435: Non-overlapping Intervals
# LeetCode 452: Minimum Arrows to Burst Balloons (same greedy)
```


Why sort by end? If we sort by start, we might greedily pick a long interval that blocks many future short ones. Picking the earliest-ending interval always leaves maximum room for future selections — this is the exchange argument proof: any solution that picks a later-ending interval can be improved by swapping to the earlier-ending one without reducing the count.

## Pattern 4: Task Scheduler with Cooldown

Given tasks with a cooldown period n (same task cannot repeat within n intervals), find the minimum time to complete all tasks. Greedy: always execute the most frequent remaining task. Use a max-heap of (count, task) pairs. After executing a task, it enters a cooldown queue. Each round, execute one task from the heap (if available), advance time by 1, and release tasks from the cooldown queue.


```
import heapq
from collections import deque

def least_interval(tasks, n):
    counts = {}
    for t in tasks:
        counts[t] = counts.get(t, 0) + 1
    heap = [-c for c in counts.values()]  # max-heap (negate for Python min-heap)
    heapq.heapify(heap)
    queue = deque()  # (count, available_at_time)
    time = 0
    while heap or queue:
        time += 1
        if heap:
            cnt = heapq.heappop(heap) + 1  # execute once, increment (closer to 0)
            if cnt < 0:
                queue.append((cnt, time + n))
        if queue and queue[0][1] == time:
            heapq.heappush(heap, queue.popleft()[0])
    return time

# LeetCode 621: Task Scheduler
```


Mathematical shortcut: answer = max(len(tasks), (max_count - 1) * (n + 1) + num_tasks_with_max_count). Use this formula for O(N) solution, but the heap-based approach generalizes to variants.

## Pattern 5: Jump Game

Can you reach the last index? At each position, you can jump up to nums[i] steps. Greedy: track the furthest reachable index. For each position, if it is within reach, update the furthest. If you ever reach a position beyond the current furthest, you're stuck.


```
def can_jump(nums):
    reach = 0
    for i, jump in enumerate(nums):
        if i > reach:
            return False  # can't reach this position
        reach = max(reach, i + jump)
    return True

def jump_game_ii(nums):
    # Minimum jumps to reach end (LeetCode 45)
    jumps = 0
    current_end = 0
    farthest = 0
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = farthest
    return jumps
```


## Pattern 6: Interval Scheduling Maximization (Weighted)

When intervals have weights (profit), greedy doesn't work — you need DP. Sort by end time. For each interval, binary search for the last non-overlapping interval (latest end <= current start). dp[i] = max(dp[i-1], weight[i] + dp[last_non_overlap]). LeetCode 1235: Maximum Profit in Job Scheduling.

## Greedy Recognition Guide

- **Merge intervals**: sort by start, merge if overlap — O(N log N)

- **Minimum rooms / resources**: min-heap of end times — O(N log N)

- **Maximum non-overlapping**: sort by end, greedy select — O(N log N)

- **Task cooldown**: max-heap by frequency, advance time — O(N log N)

- **Jump game**: track furthest reach, greedy scan — O(N)

- **Weighted intervals**: greedy fails → binary search + DP — O(N log N)

## Key Problems by Pattern

- LeetCode 56: Merge Intervals

- LeetCode 57: Insert Interval

- LeetCode 252/253: Meeting Rooms I and II

- LeetCode 435: Non-Overlapping Intervals

- LeetCode 452: Minimum Arrows to Burst Balloons

- LeetCode 621: Task Scheduler

- LeetCode 55/45: Jump Game I and II

- LeetCode 1235: Maximum Profit in Job Scheduling

- [Uber Interview Guide](https://techinterview.org/uber-interview-guide/)

- [Airbnb Interview Guide](https://techinterview.org/airbnb-interview-guide/)

- [LinkedIn Interview Guide](https://techinterview.org/linkedin-interview-guide/)

- [Atlassian Interview Guide](https://techinterview.org/atlassian-interview-guide/)

- [Apple Interview Guide](https://techinterview.org/apple-interview-guide/)

## Companies That Ask This

- [Meta Interview Guide](https://techinterview.org/meta-interview-guide/)