21.03Intermediate6 topics20 min6 interactive animations

Interval scheduling

Greedy interval problems: activity selection, merging, minimum meeting rooms, interval covering, minimum arrows and the minimum number of intervals to remove.

Learning goals

Pick the right sort key (end, start or both) for each interval problem
Solve activity selection, covering and arrow problems in O(n log n)
Merge overlapping intervals and count simultaneous meetings
Reduce 'remove the fewest intervals' to activity selection

Prerequisites

Greedy fundamentalsSorting algorithmsHeaps and priority queues

Calendars, ranges of IDs, booking systems and schedulers all reduce to intervals, and almost every interval problem is solved by one sort followed by one pass, once you know which sort.

21.03.1

Activity selection

Sort by **end time** and take every interval whose start is at or after the last chosen end. Run the “Earliest finish (optimal)” preset: of 8 intervals, the algorithm chooses 3, and the log shows each rejected interval overlapping the last chosen one. The “Touching ends are compatible” preset shows the boundary rule: an interval that starts exactly when the previous one ends is allowed, so use >=.

To list the chosen intervals instead of counting them, add each to a list. If you also need the chosen intervals in their original order, remember their indices before sorting.

Java

1static List<int[]> activitySelection(int[][] intervals) {
2    int[][] a = intervals.clone();
3    Arrays.sort(a, Comparator.comparingInt(x -> x[1]));
4    List<int[]> chosen = new ArrayList<>();
5    int lastEnd = Integer.MIN_VALUE;
6    for (int[] iv : a) {
7        if (iv[0] >= lastEnd) { chosen.add(iv); lastEnd = iv[1]; }
8    }
9    return chosen;
10}

Best

O(n log n)

Average

O(n log n)

Worst

O(n log n)

Space

O(n) for the result and sorted copy

Activity selection: which greedy rule works?

Interactive · edit the input

sorted by earliest finish time

01234567891011

Setup

Sort the 8 intervals by earliest finish time (optimal). Then scan once and take every interval that starts at or after the end of the last chosen one.

Step 1 / 13

Java

1static int select(int[][] iv, int mode) {      // mode 0: earliest finish (optimal), 1: earliest start, 2: shortest
2    Comparator<int[]> rule = mode == 0 ? Comparator.comparingInt(a -> a[1])
3                           : mode == 1 ? Comparator.comparingInt(a -> a[0])
4                           : Comparator.comparingInt(a -> a[1] - a[0]);
5    Arrays.sort(iv, rule);
6    int count = 0, lastEnd = Integer.MIN_VALUE;
7    for (int[] cur : iv) {
8        if (cur[0] >= lastEnd) {                  // compatible with everything chosen so far (half-open intervals)
9            count++; lastEnd = cur[1];            // choose it
10        }                                         // otherwise skip it
11    }
12    return count;
13}

Live state

intervals

rule

earliest finish time (optimal)

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L5	intervals=8 rule=earliest finish time (optimal)	Sort the 8 intervals by earliest finish time (optimal). Then scan once and take every interval that starts at or after the end of the last chosen one.
2	L8	start=1 end=4 last end=none	[1, 4) does not overlap the last choice: take it.
3	L9	chosen=1 last end=4	Chosen A = [1, 4). The last end is now 4.
4	L8	start=3 end=5 last end=4	[3, 5) starts before 4: it overlaps a chosen interval, skip it.
5	L8	start=0 end=6 last end=4	[0, 6) starts before 4: it overlaps a chosen interval, skip it.
6	L8	start=5 end=7 last end=4	[5, 7) does not overlap the last choice: take it.
7	L9	chosen=2 last end=7	Chosen D = [5, 7). The last end is now 7.
8	L8	start=3 end=9 last end=7	[3, 9) starts before 7: it overlaps a chosen interval, skip it.
9	L8	start=5 end=9 last end=7	[5, 9) starts before 7: it overlaps a chosen interval, skip it.
10	L8	start=6 end=10 last end=7	[6, 10) starts before 7: it overlaps a chosen interval, skip it.
11	L8	start=8 end=11 last end=7	[8, 11) does not overlap the last choice: take it.
12	L9	chosen=3 last end=11	Chosen H = [8, 11). The last end is now 11.
13	L12	chosen=3 removed=5 optimum=3 return=3	Chosen 3 intervals, which is optimal (5 must be removed to leave a non-overlapping set).

21.03.2

Interval merging

To merge overlapping intervals, sort by **start** and sweep: if the next interval starts at or before the current merged interval's end, extend the end; otherwise close the current interval and start a new one. In the “Classic” preset 5 intervals become 3, and “Touching ends” shows [1,4] and [4,5] becoming [1,5].

The sort key is different from activity selection because the question is different: merging needs neighbours in start order so that anything that can overlap the current block is processed next.

Java

1static List<int[]> mergeIntervals(int[][] intervals) {
2    int[][] a = intervals.clone();
3    Arrays.sort(a, Comparator.comparingInt(x -> x[0]));      // by start
4    List<int[]> merged = new ArrayList<>();
5    for (int[] iv : a) {
6        if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < iv[0]) {
7            merged.add(new int[]{iv[0], iv[1]});             // gap: start a new block
8        } else {
9            int[] last = merged.get(merged.size() - 1);
10            last[1] = Math.max(last[1], iv[1]);              // overlap or touch: extend (nested keeps the larger end)
11        }
12    }
13    return merged;
14}

Best

O(n log n)

Average

O(n log n)

Worst

O(n log n)

Space

O(n)

Merge overlapping intervals (sort by start, then scan)

Interactive · edit the input

input

[8, 10]

[1, 3]

[15, 18]

[2, 6]

[9, 12]

0123456789101112131415161718

Setup

In input order, overlaps can be far apart. Sorting by start puts every overlap next to its neighbour.

Step 1 / 13

Java

1public static List<int[]> merge(int[][] intervals) {
2    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));   // sort by start
3    List<int[]> merged = new ArrayList<>();
4    for (int[] cur : intervals) {
5        int[] last = merged.isEmpty() ? null : merged.get(merged.size() - 1);
6        if (last != null && cur[0] <= last[1]) {
7            last[1] = Math.max(last[1], cur[1]);     // overlap: extend
8        } else {
9            merged.add(cur);                         // gap: start a new interval
10        }
11    }
12    return merged;
13}

Live state

0 comparisons

intervals

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L1	intervals=5	In input order, overlaps can be far apart. Sorting by start puts every overlap next to its neighbour.
2	L2	intervals=5	Sorted by start: O(n log n). Now one left-to-right scan is enough.
3	L6	start=1 end=3 last end=none	Nothing merged yet: this interval starts the list.
4	L9	merged=1	Append [1, 3] as a new merged interval.
5	L6	start=2 end=6 last end=3	[2, 6] starts before the last merged interval ends, so they overlap.
6	L7	last end=6	Extend the last interval: end = max(3, 6) = 6.
7	L6	start=8 end=10 last end=6	[8, 10] starts after 6: there is a gap.
8	L9	merged=2	Append [8, 10] as a new merged interval.
9	L6	start=9 end=12 last end=10	[9, 12] starts before the last merged interval ends, so they overlap.
10	L7	last end=12	Extend the last interval: end = max(10, 12) = 12.
11	L6	start=15 end=18 last end=12	[15, 18] starts after 12: there is a gap.
12	L9	merged=3	Append [15, 18] as a new merged interval.
13	L12	return=[1,6] [8,12] [15,18]	5 intervals became 3. O(n log n) for the sort plus O(n) for the scan.

21.03.3

Minimum meeting rooms

How many rooms are needed so no two overlapping meetings share one? Sort meetings by start and keep a **min-heap of end times**, one entry per room in use. For each meeting, if the earliest-ending room is free (its end is at or before this start) reuse it by removing that end, then add this meeting's end. The heap size at the end is the number of rooms.

The “Classic” preset needs 3 rooms: at time 15 the meetings [0,30], [10,25] and [15,20] all overlap. “Back to back” needs only 1 because a meeting may start exactly when another ends. The answer equals the maximum number of meetings overlapping at any instant, which Chapter 22 computes with an event sweep.

Java

1static int minMeetingRooms(int[][] meetings) {
2    int[][] a = meetings.clone();
3    Arrays.sort(a, Comparator.comparingInt(x -> x[0]));
4    PriorityQueue<Integer> endTimes = new PriorityQueue<>();
5    for (int[] m : a) {
6        if (!endTimes.isEmpty() && endTimes.peek() <= m[0]) endTimes.poll();   // reuse the room that frees first
7        endTimes.add(m[1]);
8    }
9    return endTimes.size();
10}

Best

O(n log n)

Average

O(n log n)

Worst

O(n log n)

Space

O(n) for the heap

Minimum meeting rooms (sweep sorted events)

Interactive · edit the input

t=0

meetings

[0, 30]

[5, 10]

[10, 25]

[15, 20]

[22, 28]

0123456789101112131415161718192021222324252627282930

starts (sorted)

ends (sorted)

Setup

Only the times matter, not which meeting is which. Sort starts and ends separately and sweep left to right.

Step 1 / 9

Java

1public static int minRooms(int[][] meetings) {     // [start, end), end is exclusive
2    int n = meetings.length;
3    int[] starts = new int[n], ends = new int[n];
4    for (int i = 0; i < n; i++) { starts[i] = meetings[i][0]; ends[i] = meetings[i][1]; }
5    Arrays.sort(starts);
6    Arrays.sort(ends);
7    int rooms = 0, best = 0, e = 0;
8    for (int s = 0; s < n; s++) {
9        while (ends[e] <= starts[s]) { e++; rooms--; }   // meetings that ended free a room
10        rooms++;
11        best = Math.max(best, rooms);
12    }
13    return best;
14}

Live state

0 events

rooms

best

No condition evaluated on this step

Execution trace (dry run table)Show 9 steps

Step	Line	State	What happens
1	L5	rooms=0 best=0	Only the times matter, not which meeting is which. Sort starts and ends separately and sweep left to right.
2	L11	time=0 rooms=1 best=1	A meeting starts at 0: 1 room in use. Peak so far 1.
3	L11	time=5 rooms=2 best=2	A meeting starts at 5: 2 rooms in use. Peak so far 2.
4	L9	time=10 rooms=1 best=2	A meeting ended at 10 ≤ 10: its room is free again.
5	L11	time=10 rooms=2 best=2	A meeting starts at 10: 2 rooms in use. Peak so far 2.
6	L11	time=15 rooms=3 best=3	A meeting starts at 15: 3 rooms in use. Peak so far 3.
7	L9	time=22 rooms=2 best=3	A meeting ended at 20 ≤ 22: its room is free again.
8	L11	time=22 rooms=3 best=3	A meeting starts at 22: 3 rooms in use. Peak so far 3.
9	L13	return=3	3 rooms needed: the maximum number of meetings overlapping at any moment. O(n log n).

21.03.4

Interval covering

Given intervals and a target range [lo, hi], choose the fewest intervals whose union covers the range. Sort by start. Keep reach, the right end of the covered part (initially lo). At each round look at **all** intervals starting at or before reach and take the one with the largest end. If none extends the reach, the range has a gap and the answer is impossible.

The “Needs four” preset covers [0, 12] with 4 intervals, “One interval is enough” shows an early wide interval swallowing the rest, and “Gap: impossible” returns -1 because nothing starts at or before the reach 3 and extends it past the hole.

Java

1static int minCover(int[][] intervals, int lo, int hi) {
2    int[][] a = intervals.clone();
3    Arrays.sort(a, Comparator.comparingInt(x -> x[0]));
4    int reach = lo, used = 0, i = 0;
5    while (reach < hi) {
6        int best = reach;
7        while (i < a.length && a[i][0] <= reach) { best = Math.max(best, a[i][1]); i++; }
8        if (best == reach) return -1;                        // nothing extends the covered range
9        reach = best;
10        used++;
11    }
12    return used;
13}

Best

O(n log n)

Average

O(n log n)

Worst

O(n log n)

Space

O(1) beyond the sorted copy

Cover a range with the fewest intervals

Interactive · edit the input

covered to 0

sorted by start

0123456789101112

Setup

Cover [0, 12] using as few intervals as possible. Repeatedly look at every interval that starts within the covered part and take the one that reaches farthest.

Step 1 / 10

Java

1static int minCover(int[][] iv, int from, int to) {
2    Arrays.sort(iv, Comparator.comparingInt(a -> a[0]));          // by start
3    int count = 0, reach = from, i = 0;
4    while (reach < to) {
5        int farthest = reach;
6        while (i < iv.length && iv[i][0] <= reach) farthest = Math.max(farthest, iv[i++][1]);   // all intervals that start in time
7        if (farthest == reach) return -1;                            // nothing extends the covered part: a gap
8        count++; reach = farthest;                                   // take the one that reaches farthest
9    }
10    return count;
11}

Live state

from

reach

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L3	from=0 to=12 reach=0	Cover [0, 12] using as few intervals as possible. Repeatedly look at every interval that starts within the covered part and take the one that reaches farthest.
2	L6	reach=0 candidates=1 farthest=3	Intervals A start at or before 0; the farthest end among them is 3.
3	L8	count=1 reach=3	Take A: the covered part now reaches 3.
4	L6	reach=3 candidates=2 farthest=6	Intervals B, C start at or before 3; the farthest end among them is 6.
5	L8	count=2 reach=6	Take C: the covered part now reaches 6.
6	L6	reach=6 candidates=1 farthest=9	Intervals D start at or before 6; the farthest end among them is 9.
7	L8	count=3 reach=9	Take D: the covered part now reaches 9.
8	L6	reach=9 candidates=2 farthest=12	Intervals E, F start at or before 9; the farthest end among them is 12.
9	L8	count=4 reach=12	Take F: the covered part now reaches 12.
10	L10	return=4	Covered [0, 12] with 4 intervals.

21.03.5

Minimum arrows

Balloons are intervals on a line and an arrow at x bursts every balloon with start <= x <= end. The fewest arrows: sort by **end**, shoot at the first balloon's end, and skip every balloon that starts at or before that point; the next balloon that starts later needs a new arrow. This is activity selection in disguise, because a set of balloons that need different arrows is a set of pairwise disjoint intervals.

In the “Touching balloons share an arrow” preset, [1,2], [2,3], [3,4], [4,5] take 2 arrows at 2 and 4, and “All overlap” takes a single arrow.

Java

1static int minArrows(int[][] balloons) {
2    int[][] a = balloons.clone();
3    Arrays.sort(a, Comparator.comparingInt(x -> x[1]));      // compare ends without subtraction: no overflow
4    int arrows = 0;
5    long shot = Long.MIN_VALUE;
6    for (int[] b : a) {
7        if (b[0] > shot) { arrows++; shot = b[1]; }          // not burst by the last arrow
8    }
9    return arrows;
10}

Best

O(n log n)

Average

O(n log n)

Worst

O(n log n)

Space

O(1) beyond the sorted copy

Minimum arrows to burst all balloons

Interactive · edit the input

sorted by right end

012345678910111213141516

Setup

Sort by right end. An arrow shot at the right end of the first balloon bursts every balloon that starts at or before that point; the next unburst balloon needs a new arrow.

Step 1 / 8

Java

1static int minArrows(int[][] balloons) {
2    Arrays.sort(balloons, Comparator.comparingInt(a -> a[1]));      // by right end (compare, never subtract)
3    int arrows = 0; long shot = Long.MIN_VALUE;
4    for (int[] b : balloons) {
5        if (b[0] > shot) {                                          // not burst by the previous arrow
6            arrows++; shot = b[1];                                  // shoot at its right end
7        }
8    }
9    return arrows;
10}

Live state

balloons

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L2	balloons=4	Sort by right end. An arrow shot at the right end of the first balloon bursts every balloon that starts at or before that point; the next unburst balloon needs a new arrow.
2	L5	start=1 end=6 last arrow=none	Balloon C starts after the last arrow: it was not burst, so a new arrow is needed.
3	L6	arrows=1 last arrow=6	Shoot an arrow at 6, the right end of C: it also bursts every later balloon that starts by 6.
4	L5	start=2 end=8 last arrow=6	Balloon B contains the last arrow's position 6: already burst.
5	L5	start=7 end=12 last arrow=6	Balloon D starts after the last arrow: it was not burst, so a new arrow is needed.
6	L6	arrows=2 last arrow=12	Shoot an arrow at 12, the right end of D: it also bursts every later balloon that starts by 12.
7	L5	start=10 end=16 last arrow=12	Balloon A contains the last arrow's position 12: already burst.
8	L9	return=2	2 arrows at [6, 12].

21.03.6

Non-overlapping intervals

'Remove the fewest intervals so the rest do not overlap' is the complement of activity selection: keep the largest non-overlapping set, and the answer is n - kept. No new algorithm is needed.

The animation reports exactly that quantity at the end of each run (for example, the Earliest finish preset keeps 3 of 8, so 5 must be removed). When duplicates or touching intervals appear, the boundary rule start >= lastEnd decides whether touching intervals count as overlapping.

Java

1static int eraseOverlapIntervals(int[][] intervals) {
2    if (intervals.length == 0) return 0;
3    int[][] a = intervals.clone();
4    Arrays.sort(a, Comparator.comparingInt(x -> x[1]));
5    int kept = 1, lastEnd = a[0][1];
6    for (int i = 1; i < a.length; i++) {
7        if (a[i][0] >= lastEnd) { kept++; lastEnd = a[i][1]; }
8    }
9    return a.length - kept;
10}

Best

O(n log n)

Average

O(n log n)

Worst

O(n log n)

Space

O(1) beyond the sorted copy

Activity selection: which greedy rule works?

Interactive · edit the input

sorted by earliest finish time

01234567891011

Setup

Sort the 8 intervals by earliest finish time (optimal). Then scan once and take every interval that starts at or after the end of the last chosen one.

Step 1 / 13

Java

1static int select(int[][] iv, int mode) {      // mode 0: earliest finish (optimal), 1: earliest start, 2: shortest
2    Comparator<int[]> rule = mode == 0 ? Comparator.comparingInt(a -> a[1])
3                           : mode == 1 ? Comparator.comparingInt(a -> a[0])
4                           : Comparator.comparingInt(a -> a[1] - a[0]);
5    Arrays.sort(iv, rule);
6    int count = 0, lastEnd = Integer.MIN_VALUE;
7    for (int[] cur : iv) {
8        if (cur[0] >= lastEnd) {                  // compatible with everything chosen so far (half-open intervals)
9            count++; lastEnd = cur[1];            // choose it
10        }                                         // otherwise skip it
11    }
12    return count;
13}

Live state

intervals

rule

earliest finish time (optimal)

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L5	intervals=8 rule=earliest finish time (optimal)	Sort the 8 intervals by earliest finish time (optimal). Then scan once and take every interval that starts at or after the end of the last chosen one.
2	L8	start=1 end=4 last end=none	[1, 4) does not overlap the last choice: take it.
3	L9	chosen=1 last end=4	Chosen A = [1, 4). The last end is now 4.
4	L8	start=3 end=5 last end=4	[3, 5) starts before 4: it overlaps a chosen interval, skip it.
5	L8	start=0 end=6 last end=4	[0, 6) starts before 4: it overlaps a chosen interval, skip it.
6	L8	start=5 end=7 last end=4	[5, 7) does not overlap the last choice: take it.
7	L9	chosen=2 last end=7	Chosen D = [5, 7). The last end is now 7.
8	L8	start=3 end=9 last end=7	[3, 9) starts before 7: it overlaps a chosen interval, skip it.
9	L8	start=5 end=9 last end=7	[5, 9) starts before 7: it overlaps a chosen interval, skip it.
10	L8	start=6 end=10 last end=7	[6, 10) starts before 7: it overlaps a chosen interval, skip it.
11	L8	start=8 end=11 last end=7	[8, 11) does not overlap the last choice: take it.
12	L9	chosen=3 last end=11	Chosen H = [8, 11). The last end is now 11.
13	L12	chosen=3 removed=5 optimum=3 return=3	Chosen 3 intervals, which is optimal (5 must be removed to leave a non-overlapping set).

Practice ladder

Now try it yourself

Easy

Meeting Rooms
Merge Intervals (small inputs by hand)

Medium

Non-overlapping Intervals
Minimum Number of Arrows to Burst Balloons
Meeting Rooms II
Video Stitching

Advanced

Minimum Number of Taps to Open to Water a Garden
Maximum Profit in Job Scheduling

Key takeaways

Activity selection and the problems that reduce to it sort by end time; merging sorts by start time.
Meeting rooms needs a min-heap of end times, or equivalently an event sweep for the maximum overlap.
Covering keeps the reach and takes the farthest-reaching interval that starts within it.
Minimum arrows and minimum removals are activity selection with a different final answer.
Decide up front whether touching endpoints overlap; it is the most common off-by-one in this topic.