GreedyAlgorithmaka weighted interval scheduling, interval partitioning, meeting rooms

Interval Scheduling

The family of interval problems: unweighted selection (greedy by finish), interval partitioning into minimum rooms (greedy by start with a min-heap), and weighted selection (DP with binary search).

Pattern: Heap / Priority QueuePractice (4)
Progress

Overview

Three closely related problems appear under this name, and knowing which greedy rule applies to which is the point. Unweighted selection (maximize count) is Activity Selection: sort by finish, take greedily. Interval partitioning (minimum number of rooms so every interval gets a room) is solved by sorting by start and assigning each interval to any room that is free, tracked with a Min-Heap of room end times; the answer equals the maximum depth of overlap. Weighted selection (maximize total weight) has no greedy solution; it is O(n log n) DP: dp[i] = max(dp[i−1], w_i + dp[p(i)]) where p(i) is the last interval finishing before i starts, found by Binary Search.

The partitioning greedy is optimal because the number of rooms it opens equals the maximum number of intervals alive at one instant, which is an obvious lower bound.

greedyintervalsheapsweep linebinary searchDP

Intuition

A mental model before the formal terms.

Rooms: process meetings in start order. When a meeting starts, look at the room that frees up earliest. If it is free, reuse it; if not, every room is busy right now, so a new room is unavoidable — and at that moment you can see all the rooms overlapping at once.

Weighted: at each interval you either skip it (keep the best so far) or take it, in which case you are back to the best answer over intervals ending before it starts. Greedy cannot decide that without knowing the future, so you tabulate.

How it works

  1. Partitioning: sort by start. Maintain a min-heap of end times of occupied rooms. For each interval, if heap.top ≤ start, pop (room freed); push the interval's end. The heap's maximum size is the number of rooms.
  2. Weighted: sort by finish. For each i, find p(i) = largest j < i with finish_j ≤ start_i via binary search on finish times. dp[i] = max(dp[i−1], w_i + dp[p(i)]); dp[0] = 0.
  3. Unweighted: see Activity Selection.

Why it works

Partitioning lower bound / greedy-choice. If k intervals all contain some instant t, any schedule needs ≥ k rooms. The greedy opens a new room only when the interval starting now conflicts with every existing room, i.e. all rooms' intervals contain the current start t — so at that instant depth is rooms + 1. Hence rooms opened ≤ max depth ≤ optimum; greedy is optimal. Sorting by start is essential: it guarantees that a room is busy only if its interval contains t.

Weighted DP. The last interval (in finish order) is either in the optimal set or not. If not, the answer is dp[n−1]. If yes, all other chosen intervals finish before it starts, so they form an optimal solution to the prefix 1..p(n). This exhaustive case split is the recurrence; greedy fails because "take or skip" depends on dp[p(i)], a global quantity.

Recognition

How to tell a problem wants this.

  • "Minimum number of rooms / platforms / machines" → partitioning (heap or sweep).
  • "Maximum total value / profit of non-overlapping jobs" → weighted DP.
  • "Maximum number of non-overlapping" → unweighted greedy.
  • "Can one person attend all meetings" → sort by start and check adjacent overlap.
“k most frequent” → Heap / Priority Queue“number of ways” → Dynamic Programming“maximum number of non-overlapping” → Greedy“overlapping intervals” → Intervals

Interactive visualization

Play, step, change the input. ← → and space work too.

No interactive visualization for this topic yet

Related visualizations are linked under Related.

Pseudocode

1# partitioning: minimum rooms
2sort by start; heap = []
3for (s, e) in intervals:
4  if heap and heap.top <= s: heap.pop()
5  heap.push(e)
6  rooms = max(rooms, len(heap))
7 
8# weighted selection
9sort by finish; dp[0] = 0
10for i in 1..n: p = last j < i with finish[j] <= start[i]  (binary search)
11  dp[i] = max(dp[i-1], w[i] + dp[p])

Implementations

1import heapq
2from bisect import bisect_right
3from typing import NamedTuple
4 
5# The interval family: three problems that look alike and need three different
6# tools. Intervals are [start, end) — touching is not overlapping.
7 
8 
9class Interval(NamedTuple):
10    start: int
11    end: int
12    weight: int = 0
13 
14 
151 · UNWEIGHTED selection — greedy by earliest END. Maximum count.
16def max_non_overlapping(iv: list[Interval]) -> int:
17    count = 0
18    last_end = float("-inf")
19    for x in sorted(iv, key=lambda v: v.end):
20        if x.start >= last_end:
21            count += 1
22            last_end = x.end
23    return count
24 
25 
262 · PARTITIONING — minimum rooms. Greedy by earliest START plus a min-heap
27# of the end times currently in use; the heap size is the answer.
28def min_rooms(iv: list[Interval]) -> int:
29    heap: list[int] = []  # end times of the rooms currently in use
30    for x in sorted(iv, key=lambda v: v.start):
31        # A room frees up whenever its meeting ended at or before this start
32        if heap and heap[0] <= x.start:
33            heapq.heappop(heap)
34        heapq.heappush(heap, x.end)
35    return len(heap)
36 
37 
383 · The partitioning answer equals the maximum number of intervals
39# overlapping at any single point — the "depth" of the arrangement
40def max_depth(iv: list[Interval]) -> int:
41    events: list[tuple[int, int]] = []
42    for x in iv:
43        events.append((x.start, 1))
44        events.append((x.end, -1))
45    # ends before starts at the same time, since [a,b) and [b,c) do not overlap
46    events.sort()  # (time, delta): -1 sorts before +1 at equal times
47    cur = best = 0
48    for _, delta in events:
49        cur += delta
50        best = max(best, cur)
51    return best
52 
53 
544 · WEIGHTED selection — greedy fails, so this is DP plus a binary search
55# for the last interval that ends at or before the current one starts
56def max_weight(iv: list[Interval]) -> int:
57    ordered = sorted(iv, key=lambda v: v.end)
58    n = len(ordered)
59    ends = [x.end for x in ordered]
60    dp = [0] * (n + 1)
61    for i, x in enumerate(ordered):
625 · p = number of intervals fully before ordered[i]; take it or skip it
63        p = bisect_right(ends, x.start, 0, i)
64        dp[i + 1] = max(dp[i], dp[p] + x.weight)
65    return dp[n]
Walkthrough
  1. heapq supplies the min-heap directly, so min_rooms is six lines — the shortest of the four versions by a wide margin.
  2. events.sort() with no key works because tuples compare lexicographically and -1 < 1, so ends sort before starts at equal times automatically. That is a real convenience, and it is also a trap if the delta encoding is ever flipped.
  3. bisect_right(ends, x.start, 0, i) searches only the prefix [0, i) and returns the count of intervals ending at or before this start — the lo/hi arguments avoid slicing.
  4. Interval(NamedTuple) with weight: int = 0 gives a default so the unweighted problems can construct two-field intervals.
  5. sorted(iv, key=...) copies in every function, so none of them mutates the caller.
Complexity (this implementation)
time O(n log n) for all four · space O(n)
Language notes
  • heapq is a min-heap, which is exactly what room-freeing wants — no comparator inversion, unlike C++.
  • Tuple lexicographic comparison makes the bare events.sort() correct here, but it is worth a comment because the correctness depends on -1 < 1, not on any explicit intent.
  • bisect_right versus bisect_left is the half-open-versus-closed decision, and the lo/hi parameters keep it allocation-free.
  • NamedTuple field defaults must come last, which is why weight is the third field rather than the second.
Common mistakes in this language
  • Relying on events.sort() without understanding that the tie-break comes from -1 < 1 — flipping the delta encoding silently breaks it.
  • Using bisect_left and dropping an interval that ends exactly when the next starts.
  • Slicing ends[:i] for the binary search instead of passing hi=i, which allocates on every iteration.
Language differences that matter here
  • The min-heap decides the length of minRooms: heapq makes it six lines in Python, std::priority_queue (with std::greater) makes it eight in C++, and JS/TS carry a 25-line inline heap.
  • Binary search on the prefix is a library call with bounds in Python (bisect_right(ends, x, 0, i)) and C++ (upper_bound(begin, begin+i, x)), and hand-written in JS/TS.
  • Event-sweep tie-breaking is automatic in Python (tuples compare lexicographically and -1 < 1) and needs an explicit comparator in C++ and JS/TS — where JavaScript would otherwise stringify the pairs.
  • Every language must copy before sorting to stay side-effect free, but only Python gets it by default through sorted() versus list.sort().

Complexity

Best
—
Average
—
Worst
O(n log n)
Space
O(n)

Partitioning: sort + n heap operations. Weighted: sort + n binary searches + O(n) DP table.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Minimum resources for a set of time intervals (rooms, platforms, CPUs).
  • Maximum-weight compatible subset of intervals (weighted jobs).
  • Any sweep over interval endpoints where the relevant state is "how many are open right now".
Avoid it when
  • Greedy by finish time on weighted intervals: jobs [1,4] w=3, [3,5] w=5, [0,6] w=8. Earliest-finish takes [1,4] then nothing compatible (total 3); optimum is [0,6] with 8. Use the DP.
  • Partitioning with intervals sorted by finish instead of start: [1,10], [2,3], [4,5] in finish order puts [2,3] and [4,5] in room 1, then [1,10] conflicts — still 2, but with [1,3],[2,4],[3,5]… the finish-order assignment can over-allocate. Start order is the one with the proof.
  • Intervals with resource capacities or precedence constraints — general scheduling is NP-hard; use search or ILP.

Alternatives

Activity SelectionMerge IntervalsInterval (Range) DPPriority Queue

Common mistakes

  • Popping only one room per interval is correct; popping all free rooms is also correct but a common source of off-by-one when counting.
  • Using < instead of ≤ when an interval may start exactly when another ends.
  • In the weighted DP, binary-searching for finish < start when the problem allows touching (finish ≤ start), or searching over unsorted finishes.
  • Forgetting that p(i) must be searched among jobs before i in finish order.

Interview patterns

  • Meeting Rooms I (sort and check adjacent), II (heap or sweep of +1/−1 events).
  • Maximum Profit in Job Scheduling: weighted DP with binary search.
  • Minimum platforms / car fleet style sweeps: sort events, track open count.
Interview questions on this
Mock interviews

Example problems

Interval List IntersectionsmediumCar FleetmediumMeeting Rooms IImediumNon-overlapping Intervalsmedium