Skip to content
Tutorials Center
My learning

Topics

Lesson 168 of 225 ยท Greedy Algorithms

Interval Scheduling and Meeting Rooms

Solve interval problems in Python: activity selection, minimum platforms and meeting rooms, merge intervals and non-overlapping intervals with greedy sorting.

Calendars, flight gates, lecture halls, CPU time slices, and even booking a conference room are all about intervals: a start and an end on a timeline. Interval problems are the best showcase for greedy algorithms, because a single well-chosen sort turns messy overlapping data into something you can scan in one pass. They are also among the most common interview questions.

This lesson solves four families: activity selection (attend as many events as possible), non-overlapping intervals (remove as few as possible), merge intervals, and minimum platforms / meeting rooms (how many rooms do we need at once?). The same three ideas drive all of them: sort, scan, and compare with the last thing you kept.

Setting up: what does "overlap" mean?

We write an interval as (start, end). Two intervals overlap when each starts before the other ends. Whether touching endpoints count is a rule you must read in the problem statement. In this lesson (1, 3) and (3, 5) do not overlap: a meeting can start the moment the previous one ends.

TEXT
time ->   1   2   3   4   5   6   7
A:        [-------)                      (1, 3)
B:                [-------)              (3, 5)    touches A, no overlap
C:            [-----------)              (2, 5)    overlaps A and B

The test for overlap is a.start < b.end and b.start < a.end. If the problem says touching counts as overlap, change < to <=.

Activity selection

You are given n events, each with a start and end time. You can attend only one at a time. Pick the largest set of events that do not overlap.

Brute force. Try every subset, keep the biggest valid one. That is O(2^n): hopeless beyond n of about 25. A recursion that sorts by start time and decides "take or skip" for each event is faster than raw subsets but is still exponential without memoisation.

Which greedy rule? There are several tempting rules:

Rule Correct? Why it fails
Earliest start first No One very long early event blocks everything
Shortest event first No A short event in the middle can block two others
Fewest conflicts first No Needs a trickier counterexample, but exists
Earliest end first Yes Leaves the most room for the future

The winning rule: sort by end time; repeatedly take the event that ends first among those that do not overlap what you already took. Exchange argument: in any optimal schedule, replace its first event by the event with the earliest end overall. It ends no later, so everything after it still fits, and the schedule is just as large.

TEXT
events sorted by end:

 a: [1----4)
 b: [3------6)
 c: [0----------------------9)
 d: [5--7)
 e: [8--9)    ...

take a (ends 4). skip b (starts 3 < 4). skip c. take d (starts 5 >= 4, ends 7).
take e (starts 8 >= 7). result: a, d, e
Python Activity selection by earliest end, with a brute force check

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Sorting costs O(n log n) and the scan is O(n), so the total is O(n log n) time and O(n) space for the sorted copy. Earliest start picks (0, 9) first and gets stuck with a single event, which shows why the rule matters.

Weighted version: where greedy stops working

If each event has a profit and you want the maximum total profit rather than the maximum count, earliest-end greedy fails. You need DP: sort by end, and for each event choose between skipping it or taking it plus the best result among events that end before it starts (found with binary search). That is weighted interval scheduling, O(n log n), and a good example of where greedy gives way to DP.

Non-overlapping intervals (fewest removals)

Given intervals, what is the minimum number you must remove so that the rest do not overlap?

This is the same problem in disguise. Keeping as many as possible is activity selection, so:

TEXT
removals = n - (size of the largest non-overlapping set)
Python Minimum number of intervals to remove

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Merge intervals

Given a list of intervals, merge all overlapping ones into a minimal list. Think of highlighting time ranges on a calendar.

Brute force. Repeatedly look for any two overlapping intervals, merge them, and start over: O(n^2) or worse.

Better. Sort by start time. Then any interval that overlaps the previous merged one must start at or before the previous end. Scan once:

TEXT
sorted: (1,3) (2,6) (8,10) (9,12) (15,18)

merged = [(1,3)]
(2,6):   2 <= 3  -> extend end to max(3,6) = 6     merged = [(1,6)]
(8,10):  8 > 6   -> new interval                   merged = [(1,6), (8,10)]
(9,12):  9 <= 10 -> extend to 12                   merged = [(1,6), (8,12)]
(15,18): 15 > 12 -> new                            merged = [(1,6), (8,12), (15,18)]

Notice that this time we sort by start, not end. Here the question is different (we are combining, not choosing), and sorting by start guarantees that anything which might merge with the current block comes next.

Python Merge overlapping intervals

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Note that this problem treats touching intervals as mergeable (start <= last end), a different rule from activity selection. Always check the statement. Complexity: O(n log n) for the sort and O(n) for the scan; O(n) extra space for the output.

A related task is inserting one new interval into an already sorted, merged list. Because the list is sorted you can do it in O(n) with three phases: copy the intervals that end before the new one starts, merge everything that overlaps it, then copy the rest.

Minimum platforms and meeting rooms

Given arrival and departure times of trains, what is the minimum number of platforms so that no train waits? It is the same question as "how many meeting rooms are needed for these meetings?": the answer is the maximum number of intervals alive at the same moment.

Brute force. For each interval's start time, count how many intervals contain it; the maximum count is the answer. That is O(n^2).

Sweep line. Break each interval into two events: an arrival (+1) at the start and a departure (-1) at the end. Sort all events by time and scan, keeping a running count. The maximum count seen is the answer. With touching allowed, process departures before arrivals at the same time.

TEXT
meetings: (0,30) (5,10) (15,20)

events sorted: 0:+1  5:+1  10:-1  15:+1  20:-1  30:-1
running count: 1     2     1      2      1      0
maximum = 2 rooms
Python Minimum meeting rooms with a sweep line

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The sort puts the tuple (time, -1) before (time, 1), which is exactly the "free the room first" rule. Complexity: O(n log n) time, O(n) space.

The same answer with a min-heap

An alternative that also assigns meetings to concrete rooms: sort meetings by start time and keep a min-heap of the end times of the rooms in use. For each meeting, if the earliest-finishing room is free by its start, reuse it (pop); then push this meeting's end. The size of the heap at the end is the number of rooms.

Python Meeting rooms with a heap of end times

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each meeting does one push and at most one pop, each O(log n), so this is also O(n log n). Use the sweep when you only need the count; use the heap when you need the schedule.

Choosing the right sort key

Problem Sort by Why
Maximum number of non-overlapping intervals end time finishing early leaves the most room
Merge overlapping intervals start time neighbours in the sorted order are the only merge candidates
Minimum rooms / platforms start (heap) or events by time (sweep) you track what is alive at each moment
Minimum arrows to burst balloons (intervals on a line) end time shoot at the earliest end, popping everything that contains it
Weighted intervals end time, then DP greedy no longer works

Common mistakes

  • Wrong sort key. Sorting by start for activity selection quietly gives wrong answers on long early events.
  • Touching intervals. Merging with < where the problem wants <= (or the opposite) fails exactly the edge tests. Decide per problem.
  • Mutating while merging. If your input intervals are shared lists, merged[-1][1] = ... changes the original. Copy when needed.
  • Event ties. In a sweep, at equal times process departures before arrivals when back-to-back is allowed; the tuple sort order above does that.
  • Forgetting empty input. Handle [] explicitly.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which sort key makes the greedy for activity selection correct?

    Choosing the event that ends first leaves the maximum room for the remaining events.
  2. 2. Minimum number of intervals to remove so the rest do not overlap, given n intervals?

    Keeping the most intervals is activity selection; everything else must be removed.
  3. 3. Merge intervals: after sorting by start, when does the next interval merge into the last one?

    Sorted by start, an interval overlaps the current block exactly when it starts before or at the block's end; then extend the block to the larger end.
  4. 4. What does the minimum number of meeting rooms equal?

    At the busiest moment every simultaneous meeting needs its own room, and that many rooms suffice.
  5. 5. What is the time complexity of the sweep-line solution?

    Sorting the 2n events dominates; the scan is linear.

Summary

  • Intervals are (start, end); decide up front whether touching endpoints overlap.
  • Activity selection: sort by end time, take every event that starts at or after the last chosen end; O(n log n). Earliest start and shortest first are wrong.
  • Fewest removals = n minus the maximum non-overlapping set.
  • Merge intervals: sort by start and extend the last block while start <= last end.
  • Minimum rooms or platforms = maximum overlap, computed by a sweep over sorted +1/-1 events or by a min-heap of end times.
  • Weighted interval scheduling needs DP instead of greedy.

Next: Huffman Coding