22.02Intermediate6 topics21 min6 interactive animations

Fundamental interval problems

The standard interval problems: merging, inserting, erasing overlaps, intersecting two lists, meeting rooms and scheduling, with the technique each one needs.

Learning goals

Merge a list of intervals and insert one into a sorted list in a single pass
Remove the fewest intervals to eliminate overlaps
Intersect two sorted lists of disjoint intervals with two pointers
Check meeting conflicts and compute the rooms required
Pick between greedy and dynamic programming for weighted scheduling

Prerequisites

Interval modelingGreedy interval scheduling

These six problems cover most of what interval questions ask for. Once each one is clear, new variations are combinations of them.

22.02.1

Merge intervals

Sort by start and sweep, extending the last merged interval whenever the next interval starts at or before its end. In the “Classic” preset, 5 intervals become 3. “Nested” shows why you extend with max(end, next end) instead of copying the next end: [2, 3] and [4, 8] inside [1, 10] must not shrink it.

Cost: O(n log n) for the sort and O(n) for the scan. If the input is already sorted by start, only the scan remains.

Java

1static int[][] merge(int[][] intervals) {
2    int[][] a = intervals.clone();
3    Arrays.sort(a, Comparator.comparingInt(x -> x[0]));
4    List<int[]> out = new ArrayList<>();
5    for (int[] iv : a) {
6        if (out.isEmpty() || out.get(out.size() - 1)[1] < iv[0]) out.add(new int[]{iv[0], iv[1]});
7        else out.get(out.size() - 1)[1] = Math.max(out.get(out.size() - 1)[1], iv[1]);   // closed: touching merges
8    }
9    return out.toArray(new int[0][]);
10}

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.

22.02.2

Insert interval

Insert a new interval into a sorted, disjoint list and merge as needed, in a single pass without sorting again. Split the scan into three phases: copy everything that ends before the new interval starts, merge every interval that overlaps it into the new one (taking the smaller start and larger end), then copy the rest.

In the “Merges two” preset, inserting [2, 7] into [1,3], [6,9], [12,15] absorbs the first two and leaves [[1, 9], [12, 15]]. “Fits in a gap” inserts [4, 5] between [1,3] and [6,9] with no merging, and “Swallows everything” collapses the whole list.

Java

1static int[][] insert(int[][] sorted, int[] add) {
2    List<int[]> out = new ArrayList<>();
3    int i = 0, n = sorted.length;
4    while (i < n && sorted[i][1] < add[0]) out.add(sorted[i++]);          // entirely before
5    int lo = add[0], hi = add[1];
6    while (i < n && sorted[i][0] <= hi) {                                // overlaps: absorb
7        lo = Math.min(lo, sorted[i][0]);
8        hi = Math.max(hi, sorted[i][1]);
9        i++;
10    }
11    out.add(new int[]{lo, hi});
12    while (i < n) out.add(sorted[i++]);                                  // entirely after
13    return out.toArray(new int[0][]);
14}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(n) for the output

Insert an interval into a sorted list and merge

Interactive · edit the input

list

[1, 3]

[6, 9]

[12, 15]

new

[2, 7]

result

empty

0123456789101112131415

Setup

Insert [2, 7] into the sorted list. Three zones: intervals that end before it, intervals that overlap it (merge them all), and intervals that start after it.

Step 1 / 7

Java

1static List<int[]> insert(int[][] list, int[] add) {
2    List<int[]> out = new ArrayList<>(); int i = 0, n = list.length;
3    while (i < n && list[i][1] < add[0]) out.add(list[i++]);          // entirely before the new interval
4    while (i < n && list[i][0] <= add[1]) {                           // overlaps the new interval
5        add[0] = Math.min(add[0], list[i][0]); add[1] = Math.max(add[1], list[i][1]); i++;
6    }
7    out.add(add);
8    while (i < n) out.add(list[i++]);                                 // entirely after
9    return out;
10}

Live state

intervals

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L2	intervals=3	Insert [2, 7] into the sorted list. Three zones: intervals that end before it, intervals that overlap it (merge them all), and intervals that start after it.
2	L4	interval=[1,3]	[1, 3] starts no later than the new end: they overlap, so widen the new interval.
3	L5	merged=[1,7]	The new interval is now [1, 7].
4	L4	interval=[6,9]	[6, 9] starts no later than the new end: they overlap, so widen the new interval.
5	L5	merged=[1,9]	The new interval is now [1, 9].
6	L7	added=[1,9]	Add the merged interval [1, 9] to the result.
7	L9	return=[[1, 9], [12, 15]]	Result [[1, 9], [12, 15]]. One pass: O(n), because the list was already sorted.

22.02.3

Erase overlaps

The fewest intervals to remove so that none overlap equals n minus the largest set of pairwise disjoint intervals, and that set is the activity-selection answer. Sort by end and keep an interval when its start is at or after the last kept end.

An equivalent one-pass form sorts by **start** instead and, whenever two intervals overlap, discards the one with the **larger end** (keeping the one that leaves more room). Both forms give the same count; the second needs only the current frontier end. The “Earliest finish” preset keeps 3 of 8, so 5 must be removed.

Java

1// sort by start; on overlap, drop the interval that ends later
2static int eraseOverlaps(int[][] intervals) {
3    if (intervals.length == 0) return 0;
4    int[][] a = intervals.clone();
5    Arrays.sort(a, Comparator.comparingInt(x -> x[0]));
6    int removed = 0, frontier = a[0][1];
7    for (int i = 1; i < a.length; i++) {
8        if (a[i][0] < frontier) {                            // overlap: remove the one with the larger end
9            removed++;
10            frontier = Math.min(frontier, a[i][1]);
11        } else {
12            frontier = a[i][1];
13        }
14    }
15    return removed;
16}

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).

22.02.4

Intersections

Given two lists of disjoint intervals, each sorted, find every point both cover. Use two pointers: compute the intersection of the current pair (it is non-empty when the larger start is at or before the smaller end), then advance the pointer of the interval that ends first, because it cannot intersect anything further in the other list.

The “Classic” preset (A = [0,2], [5,10], [13,23], [24,25] and B = [1,5], [8,12], [15,24], [25,26]) finds 6 intersections: [1,2], [5,5], [8,10], [15,23], [24,24] and [25,25]. Each step advances one pointer, so the cost is O(|A| + |B|), not their product. Single-point results like [5, 5] appear because the intervals are closed.

Java

1static int[][] intersections(int[][] a, int[][] b) {
2    List<int[]> out = new ArrayList<>();
3    int i = 0, j = 0;
4    while (i < a.length && j < b.length) {
5        int lo = Math.max(a[i][0], b[j][0]);
6        int hi = Math.min(a[i][1], b[j][1]);
7        if (lo <= hi) out.add(new int[]{lo, hi});            // closed intervals: a shared point counts
8        if (a[i][1] < b[j][1]) i++; else j++;                // drop the one that ends first
9    }
10    return out.toArray(new int[0][]);
11}

Best

O(a + b)

Average

O(a + b)

Worst

O(a + b)

Space

O(1) beyond the output

Intersections of two sorted interval lists

Interactive · edit the input

[0, 2]

[5, 10]

[13, 23]

[24, 25]

[1, 5]

[8, 12]

[15, 24]

[25, 26]

intersections

empty

01234567891011121314151617181920212223242526

Setup

Both lists are sorted and disjoint. Compare the current interval of each list; their overlap is [max of starts, min of ends] when that range is not empty. Then advance the interval that ends first, because it cannot overlap anything later in the other list.

Step 1 / 16

Java

1static List<int[]> intersect(int[][] a, int[][] b) {
2    List<int[]> out = new ArrayList<>(); int i = 0, j = 0;
3    while (i < a.length && j < b.length) {
4        int lo = Math.max(a[i][0], b[j][0]), hi = Math.min(a[i][1], b[j][1]);
5        if (lo <= hi) out.add(new int[]{lo, hi});                    // the overlap, if any (closed intervals)
6        if (a[i][1] < b[j][1]) i++; else j++;                        // advance the one that ends first
7    }
8    return out;
9}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 16 steps

Step	Line	State	What happens
1	L2	a=4 b=4	Both lists are sorted and disjoint. Compare the current interval of each list; their overlap is [max of starts, min of ends] when that range is not empty. Then advance the interval that ends first, because it cannot overlap anything later in the other list.
2	L5	lo=1 hi=2	[0,2] and [1,5] overlap in [1, 2].
3	L6	i=1 j=0	Advance list A: its interval ends first.
4	L5	lo=5 hi=5	[5,10] and [1,5] overlap in [5, 5].
5	L6	i=1 j=1	Advance list B: its interval ends first.
6	L5	lo=8 hi=10	[5,10] and [8,12] overlap in [8, 10].
7	L6	i=2 j=1	Advance list A: its interval ends first.
8	L5	lo=13 hi=12	[13,23] and [8,12] do not overlap (lo 13 > hi 12).
9	L6	i=2 j=2	Advance list B: its interval ends first.
10	L5	lo=15 hi=23	[13,23] and [15,24] overlap in [15, 23].
11	L6	i=3 j=2	Advance list A: its interval ends first.
12	L5	lo=24 hi=24	[24,25] and [15,24] overlap in [24, 24].
13	L6	i=3 j=3	Advance list B: its interval ends first.
14	L5	lo=25 hi=25	[24,25] and [25,26] overlap in [25, 25].
15	L6	i=4 j=3	Advance list A: its interval ends first.
16	L8	return=[[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]	6 intersections: [[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]. Each step advances one pointer, so the scan is O(\|A\| + \|B\|).

22.02.5

Meeting rooms

Two questions share one data set. **Can one person attend every meeting?** Sort by start and check that each meeting starts no earlier than the previous one ends. **How many rooms are needed?** The answer is the largest number of meetings in progress at any moment; the rooms lesson in the greedy chapter used a heap, and the event sweep in the next lesson group gets the same number from sorted endpoints.

In the “Classic” preset (0-30, 5-10, 15-20, 10-25, 22-28) three meetings run together between times 15 and 20, so 3 rooms are needed. “Back to back” needs 1 because each meeting starts when the previous one ends.

Java

1static boolean canAttendAll(int[][] meetings) {
2    int[][] a = meetings.clone();
3    Arrays.sort(a, Comparator.comparingInt(x -> x[0]));
4    for (int i = 1; i < a.length; i++) {
5        if (a[i][0] < a[i - 1][1]) return false;             // starts before the previous one ends
6    }
7    return true;
8}
9
10static int roomsNeeded(int[][] meetings) {
11    int n = meetings.length;
12    int[] start = new int[n], end = new int[n];
13    for (int i = 0; i < n; i++) { start[i] = meetings[i][0]; end[i] = meetings[i][1]; }
14    Arrays.sort(start);
15    Arrays.sort(end);
16    int rooms = 0, best = 0, j = 0;
17    for (int i = 0; i < n; i++) {
18        while (end[j] <= start[i]) { j++; rooms--; }         // meetings that finished before this one starts
19        rooms++;
20        best = Math.max(best, rooms);
21    }
22    return best;
23}

Best

O(n log n)

Average

O(n log n)

Worst

O(n log n)

Space

O(n)

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).

22.02.6

Interval scheduling

Scheduling asks you to choose intervals, and the right tool depends on what each interval is worth. With **equal value** per interval, greedy by earliest end finishes the most. With **different weights** (profits), greedy fails and dynamic programming is needed: sort by end, and for each interval either skip it or take it and add the best value achievable among intervals ending at or before its start, found by binary search.

A small counterexample shows the gap. Take A = [0, 10) with weight 10, B = [0, 4) with weight 3 and C = [5, 9) with weight 3. Earliest finish takes B and C for a total of 6, but the single interval A is worth 10.

This is a first example of dynamic programming, which Chapter 23 develops from the ground up. The code stores the best total for the first i intervals in best[i] and combines the skip and take cases.

Task	Technique	Cost
Most intervals, no overlaps	Greedy: sort by end	O(n log n)
Fewest rooms for all intervals	Sweep or heap	O(n log n)
Cover a range with the fewest intervals	Greedy: farthest reach	O(n log n)
Most profit with weights	Dynamic programming + binary search	O(n log n)

Java

1// jobs[i] = {start, end, weight}, half-open; returns the maximum total weight of disjoint jobs
2static int weightedScheduling(int[][] jobs) {
3    int[][] a = jobs.clone();
4    Arrays.sort(a, Comparator.comparingInt(x -> x[1]));      // by end
5    int n = a.length;
6    int[] best = new int[n + 1];                             // best[i]: optimum using the first i jobs
7    for (int i = 1; i <= n; i++) {
8        int lo = 0, hi = i - 1;                              // lo ends as the number of jobs among the first i-1 that end by a[i-1][0]
9        while (lo < hi) {
10            int mid = (lo + hi) >>> 1;
11            if (a[mid][1] <= a[i - 1][0]) lo = mid + 1; else hi = mid;
12        }
13        best[i] = Math.max(best[i - 1], best[lo] + a[i - 1][2]);
14    }
15    return best[n];
16}

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
Teemo Attacking

Medium

Insert Interval
Interval List Intersections
Non-overlapping Intervals
Meeting Rooms II

Advanced

Maximum Profit in Job Scheduling
Employee Free Time

Key takeaways

Merge: sort by start and extend the last block with the maximum end.
Insert into a sorted list in one pass: copy before, absorb overlaps, copy after.
Erase overlaps equals n minus the greedy activity-selection count.
Intersect two sorted lists with two pointers, advancing the one that ends first.
Weighted scheduling needs dynamic programming; unweighted scheduling is greedy.