Builds on Merge Intervals, which you haven’t finished yet.
Interval Scheduling (Activity Selection, Greedy by End Time)
You have an array of intervals intervals, each entry [start_i, end_i]. Find the fewest intervals you'd need to delete so that whatever remains has no two intervals overlapping, and return that count.
Touching at a single boundary point does not count as overlapping -- [1, 2] and [2, 3] are considered non-overlapping.
Interval Scheduling
intervals ➔ sort by end time ➔ greedily pick earliest finishing| 1 | def erase_overlap_intervals(intervals: list[list[int]]) -> int: |
| 2 | """Greedy Non-overlapping Intervals: remove minimum intervals. |
| 3 | Strategy: Sort by END time; greedily keep earliest finishing. |
| 4 | Time: O(N log N) | Space: O(N) |
| 5 | """ |
| 6 | if not intervals: |
| 7 | return 0 |
| 8 | |
| 9 | # 1. Sort by End Time and Open the First Kept Interval: |
| 10 | # Keeping whichever interval finishes earliest leaves the most room for the intervals that |
| 11 | # follow, so sorting by end time and keeping the first one is the optimal first choice. |
| 12 | intervals.sort(key=lambda iv: iv[1]) |
| 13 | removed_count = 0 |
| 14 | prev_end = intervals[0][1] # prev_end is the end of the last interval kept so far |
| 15 | |
| 16 | for start, end in intervals[1:]: |
| 17 | # 2. Drop an Overlap or Keep and Advance: |
| 18 | # start < prev_end means this interval starts before the last kept one ends, so keeping both |
| 19 | # would overlap; dropping this one is always at least as good, because it ends no earlier |
| 20 | # than the one already kept. |
| 21 | if start < prev_end: |
| 22 | removed_count += 1 # Overlap: drop incoming interval |
| 23 | else: |
| 24 | prev_end = end # Keep incoming interval, advance boundary |
| 25 | |
| 26 | return removed_count |
prev_end is the end of the last kept interval, and the kept intervals are the most that can fit among those seen so far.Sort by end time, then keep an interval whenever it starts after the last kept one ends. Finishing earliest leaves the most room for the rest, so this keeps the most intervals, and everything else is a removal. In the blueprint a kept interval moves prev_end to its end, and any interval with start < prev_end is counted in removed_count. The trap is sorting by start (key=lambda iv: iv[0]) and keeping whichever interval comes first: [1, 100] is kept and blocks [2, 3], [3, 4], ... that would fit one after another. (Sorting by start also works if, on an overlap, you keep the one that ends first; sorting by end makes that choice for you.)
See it run
Interval Scheduling, step by step
prev_end 3removed_count 0
Each column is one time point. Each row of numbers is one interval, sorted by end. A dash marks the time points the interval covers. The word keep or drop replaces the dashes after the decision.
startthe start time of the interval being checkedendthe end time of the interval being checkedprev_endthe end time of the last kept interval
Sort by end time. The first interval [2, 3] is kept, so prev_end = 3.
Gotcha 1 of 4
- The trap
Gotcha 1: Sorting by start instead of by end
Mistakeintervals.sort(key=lambda iv: iv[0])Fixintervals.sort(key=lambda iv: iv[1])What happens: Sorted by start, a long interval such as
[1, 100]can come first. The loop keeps it and setsprev_end = 100. Every short interval that starts before 100 is then removed. Sorted by end, the loop keeps the interval that finishes first and leaves the most room.Example: intervals = [[1, 100], [2, 3], [3, 4]]Mistake: returns 2Fix: returns 1
- Every interval must stay, and overlapping ones are joined into one, as in Merge Intervals (LC 56): nothing is removed, so there is no count to keep as small as possible. See Merge Intervals
- You must cover a whole range with as few intervals as possible, as in Video Stitching (LC 1024), instead of keeping as many non-overlapping intervals as possible: keeping the interval that ends earliest fails there. See Greedy
Deep Dive
Why the interval that ends first is the safe choice
This card builds on the Merge Intervals card. That card sorts by start and merges. This card sorts by end and keeps or drops each interval.
Look at the interval that ends first. Any set of non-overlapping intervals that does not use it can swap its first interval for this one. The new interval ends no later than the old one, so it overlaps nothing that the old one did not. The set keeps the same size. So some best answer always contains the interval that ends first.
After that choice, only intervals that start at or after its end can still be kept. The same argument applies to the remaining intervals. The loop does this with prev_end: it keeps an interval when start >= prev_end, then sets prev_end = end.
The most intervals that can be kept is n - removed_count, so the fewest removals is removed_count.
Example: in Non-overlapping Intervals (LC 435), intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]. Sorted by end, the order is [1, 2], [2, 3], [1, 3], [3, 4]. [1, 2] is kept, so prev_end = 2. [2, 3] starts at 2, so it is kept and prev_end = 3. [1, 3] starts at 1, which is less than 3, so it is removed. [3, 4] starts at 3, so it is kept. The answer is 1.
One trace: touching intervals are kept
The board replays intervals = [[1, 9], [2, 3], [3, 4], [1, 3]]. The rows are in sorted order by end, so the first row is [2, 3].
[2, 3] is kept, so prev_end = 3. [1, 3] starts at 1, which is less than 3, so it is removed. [3, 4] starts at 3, and 3 < 3 is false. The two intervals only touch, so [3, 4] is kept and prev_end = 4. This is the step marked as the trap on the board.
If the test were start <= prev_end, [3, 4] would be removed. Then [1, 9] would also be removed, and the loop would return 3 instead of 2. In Non-overlapping Intervals (LC 435), intervals that share only an end point do not overlap.
[1, 9] ends last. It starts at 1, which is less than 4, so it is removed. The answer is 2. Only [2, 3] and [3, 4] remain.
The trap: sorting by start
Keep the same intervals and change only the sort key to iv[0]. The order becomes [1, 9], [1, 3], [2, 3], [3, 4]. The loop keeps [1, 9] first and sets prev_end = 9. Every other interval starts before 9, so all three are removed. The loop returns 3 instead of 2.
The reason is that the first interval by start does not leave room for the others. A long interval blocks many short ones. The interval that ends first blocks the fewest.
Sorting by start can work, but it needs an extra rule. On an overlap, keep the interval with the smaller end and set prev_end = min(prev_end, end). Sorting by end makes this choice automatically.
Also read intervals[0][1] only after the sort. Before the sort, intervals[0] is the first interval of the input, and its end can be large.
The cost, and which problems fit
The sort takes O(N log N) time and the loop takes O(N) time. The total is O(N log N). The loop keeps only prev_end and removed_count, so the extra space is O(1) besides the sort.
The same keep-the-earliest-end idea solves other counting questions. Minimum Number of Arrows to Burst Balloons (LC 452) sorts by end and shoots at the end of the first balloon. Every balloon that starts at or before that point is burst with it.
Example: for LC 435 with [[1, 2], [1, 2], [1, 2]], the sorted list is the same. The first is kept, and the other two start at 1, which is less than 2. The answer is 2.
If the question asks for the largest total weight and not the largest count, this greedy choice is no longer safe. Use dynamic programming over the sorted intervals.
60-Second Pitch
"I want to keep as many non-overlapping intervals as I can, so I sort by end time. The interval that ends first leaves the most room, and any best answer can swap its first interval for it. I keep the first interval and store its end as prev_end. For each next interval, if start < prev_end it overlaps, so I remove it and add 1 to removed_count. Otherwise I keep it and set prev_end = end. The sort costs O(N log N) and the loop costs O(N), with O(1) extra space. I check that intervals that only touch are kept, so the test is < and not <=."
Common Questions
- Why sort by end time and not by start time?
The interval that ends first blocks the least time for the others. Any best answer can swap its first interval for the one that ends first, without losing a kept interval. A long interval that starts first can block many short ones, as
[1, 9]does in[[1, 9], [2, 3], [3, 4], [1, 3]].- Why is the test
start < prev_endand not<=? In Non-overlapping Intervals (LC 435), intervals that share only an end point do not overlap.
[2, 3]and[3, 4]can both be kept. With<=, the loop removes[3, 4]and returns too large a count.- What are the time and space complexity?
O(N log N)time, because of the sort. The loop isO(N). The extra space isO(1)besides the space the sort uses. The blueprint changes the caller's list by sorting it.- How do you return the kept intervals and not only the count?
Append each kept interval to a list
keptin the loop, including the first one. The loop already decides keep or drop for each interval. The length ofkeptisn - removed_count.- What changes when each interval has a different value?
The greedy choice is no longer safe, because a short interval can have a small value and block a long one with a large value. Sort by end, then use dynamic programming: for each interval, take the best of skipping it or adding its value to the best total that ends at or before its start.
SWE Reasoning
Spot it
- The question asks for the most intervals that do not overlap, or the fewest intervals to remove so that the rest do not overlap.
- Every interval has the same value, so only the count matters.
- Choosing one interval blocks the time it covers, and the other intervals compete for the time that is left.
- The question is a scheduling one: rooms, talks, jobs, or balloons shot by one arrow.
- The answer is a count, and the chosen set itself is not needed.
The invariant, step by step
- The list is empty, so return 0. Otherwise sort
intervalsbyiv[1], which is the end time. - Keep the first interval. Set
prev_end = intervals[0][1]andremoved_count = 0. - For each
start, endin the rest of the list, teststart < prev_end. - If it is true, the interval starts before the last kept interval ends. Drop it:
removed_count += 1. - Otherwise keep it:
prev_end = end. It ends no earlier than the previousprev_end, soprev_endnever moves left. prev_endis always the end of the last kept interval, and the kept set is the largest possible among the intervals seen so far.
Traps
- Sorting by start. A long interval such as
[1, 9]comes first and blocks the short ones. For[[1, 9], [2, 3], [3, 4], [1, 3]]the loop returns 3 instead of 2. - Using
<=for the overlap test. Intervals that only touch do not overlap in Non-overlapping Intervals (LC 435).[3, 4]afterprev_end = 3must be kept. - Reading
prev_endbefore the sort.intervals[0][1]must come from the sorted list. Before the sort it is the end of an arbitrary interval. - Counting the kept intervals and returning that. The question asks for the removals. Return
removed_count, orn - kept. - Moving
prev_endon a drop. A dropped interval must not changeprev_end. Only a kept interval sets it.
Practice
Builds on Merge Intervals, which you haven’t finished yet.
Interval Scheduling (Activity Selection, Greedy by End Time)
You have an array of intervals intervals, each entry [start_i, end_i]. Find the fewest intervals you'd need to delete so that whatever remains has no two intervals overlapping, and return that count.
Touching at a single boundary point does not count as overlapping -- [1, 2] and [2, 3] are considered non-overlapping.
Interval Scheduling
intervals ➔ sort by end time ➔ greedily pick earliest finishing| 1 | def erase_overlap_intervals(intervals: list[list[int]]) -> int: |
| 2 | """Greedy Non-overlapping Intervals: remove minimum intervals. |
| 3 | Strategy: Sort by END time; greedily keep earliest finishing. |
| 4 | Time: O(N log N) | Space: O(N) |
| 5 | """ |
| 6 | if not intervals: |
| 7 | return 0 |
| 8 | |
| 9 | # 1. Sort by End Time and Open the First Kept Interval: |
| 10 | # Keeping whichever interval finishes earliest leaves the most room for the intervals that |
| 11 | # follow, so sorting by end time and keeping the first one is the optimal first choice. |
| 12 | intervals.sort(key=lambda iv: iv[1]) |
| 13 | removed_count = 0 |
| 14 | prev_end = intervals[0][1] # prev_end is the end of the last interval kept so far |
| 15 | |
| 16 | for start, end in intervals[1:]: |
| 17 | # 2. Drop an Overlap or Keep and Advance: |
| 18 | # start < prev_end means this interval starts before the last kept one ends, so keeping both |
| 19 | # would overlap; dropping this one is always at least as good, because it ends no earlier |
| 20 | # than the one already kept. |
| 21 | if start < prev_end: |
| 22 | removed_count += 1 # Overlap: drop incoming interval |
| 23 | else: |
| 24 | prev_end = end # Keep incoming interval, advance boundary |
| 25 | |
| 26 | return removed_count |
prev_end is the end of the last kept interval, and the kept intervals are the most that can fit among those seen so far.Sort by end time, then keep an interval whenever it starts after the last kept one ends. Finishing earliest leaves the most room for the rest, so this keeps the most intervals, and everything else is a removal. In the blueprint a kept interval moves prev_end to its end, and any interval with start < prev_end is counted in removed_count. The trap is sorting by start (key=lambda iv: iv[0]) and keeping whichever interval comes first: [1, 100] is kept and blocks [2, 3], [3, 4], ... that would fit one after another. (Sorting by start also works if, on an overlap, you keep the one that ends first; sorting by end makes that choice for you.)
See it run
Interval Scheduling, step by step
prev_end 3removed_count 0
Each column is one time point. Each row of numbers is one interval, sorted by end. A dash marks the time points the interval covers. The word keep or drop replaces the dashes after the decision.
startthe start time of the interval being checkedendthe end time of the interval being checkedprev_endthe end time of the last kept interval
Sort by end time. The first interval [2, 3] is kept, so prev_end = 3.
Gotcha 1 of 4
- The trap
Gotcha 1: Sorting by start instead of by end
Mistakeintervals.sort(key=lambda iv: iv[0])Fixintervals.sort(key=lambda iv: iv[1])What happens: Sorted by start, a long interval such as
[1, 100]can come first. The loop keeps it and setsprev_end = 100. Every short interval that starts before 100 is then removed. Sorted by end, the loop keeps the interval that finishes first and leaves the most room.Example: intervals = [[1, 100], [2, 3], [3, 4]]Mistake: returns 2Fix: returns 1
- Every interval must stay, and overlapping ones are joined into one, as in Merge Intervals (LC 56): nothing is removed, so there is no count to keep as small as possible. See Merge Intervals
- You must cover a whole range with as few intervals as possible, as in Video Stitching (LC 1024), instead of keeping as many non-overlapping intervals as possible: keeping the interval that ends earliest fails there. See Greedy
Deep Dive
Why the interval that ends first is the safe choice
This card builds on the Merge Intervals card. That card sorts by start and merges. This card sorts by end and keeps or drops each interval.
Look at the interval that ends first. Any set of non-overlapping intervals that does not use it can swap its first interval for this one. The new interval ends no later than the old one, so it overlaps nothing that the old one did not. The set keeps the same size. So some best answer always contains the interval that ends first.
After that choice, only intervals that start at or after its end can still be kept. The same argument applies to the remaining intervals. The loop does this with prev_end: it keeps an interval when start >= prev_end, then sets prev_end = end.
The most intervals that can be kept is n - removed_count, so the fewest removals is removed_count.
Example: in Non-overlapping Intervals (LC 435), intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]. Sorted by end, the order is [1, 2], [2, 3], [1, 3], [3, 4]. [1, 2] is kept, so prev_end = 2. [2, 3] starts at 2, so it is kept and prev_end = 3. [1, 3] starts at 1, which is less than 3, so it is removed. [3, 4] starts at 3, so it is kept. The answer is 1.
One trace: touching intervals are kept
The board replays intervals = [[1, 9], [2, 3], [3, 4], [1, 3]]. The rows are in sorted order by end, so the first row is [2, 3].
[2, 3] is kept, so prev_end = 3. [1, 3] starts at 1, which is less than 3, so it is removed. [3, 4] starts at 3, and 3 < 3 is false. The two intervals only touch, so [3, 4] is kept and prev_end = 4. This is the step marked as the trap on the board.
If the test were start <= prev_end, [3, 4] would be removed. Then [1, 9] would also be removed, and the loop would return 3 instead of 2. In Non-overlapping Intervals (LC 435), intervals that share only an end point do not overlap.
[1, 9] ends last. It starts at 1, which is less than 4, so it is removed. The answer is 2. Only [2, 3] and [3, 4] remain.
The trap: sorting by start
Keep the same intervals and change only the sort key to iv[0]. The order becomes [1, 9], [1, 3], [2, 3], [3, 4]. The loop keeps [1, 9] first and sets prev_end = 9. Every other interval starts before 9, so all three are removed. The loop returns 3 instead of 2.
The reason is that the first interval by start does not leave room for the others. A long interval blocks many short ones. The interval that ends first blocks the fewest.
Sorting by start can work, but it needs an extra rule. On an overlap, keep the interval with the smaller end and set prev_end = min(prev_end, end). Sorting by end makes this choice automatically.
Also read intervals[0][1] only after the sort. Before the sort, intervals[0] is the first interval of the input, and its end can be large.
The cost, and which problems fit
The sort takes O(N log N) time and the loop takes O(N) time. The total is O(N log N). The loop keeps only prev_end and removed_count, so the extra space is O(1) besides the sort.
The same keep-the-earliest-end idea solves other counting questions. Minimum Number of Arrows to Burst Balloons (LC 452) sorts by end and shoots at the end of the first balloon. Every balloon that starts at or before that point is burst with it.
Example: for LC 435 with [[1, 2], [1, 2], [1, 2]], the sorted list is the same. The first is kept, and the other two start at 1, which is less than 2. The answer is 2.
If the question asks for the largest total weight and not the largest count, this greedy choice is no longer safe. Use dynamic programming over the sorted intervals.
60-Second Pitch
"I want to keep as many non-overlapping intervals as I can, so I sort by end time. The interval that ends first leaves the most room, and any best answer can swap its first interval for it. I keep the first interval and store its end as prev_end. For each next interval, if start < prev_end it overlaps, so I remove it and add 1 to removed_count. Otherwise I keep it and set prev_end = end. The sort costs O(N log N) and the loop costs O(N), with O(1) extra space. I check that intervals that only touch are kept, so the test is < and not <=."
Common Questions
- Why sort by end time and not by start time?
The interval that ends first blocks the least time for the others. Any best answer can swap its first interval for the one that ends first, without losing a kept interval. A long interval that starts first can block many short ones, as
[1, 9]does in[[1, 9], [2, 3], [3, 4], [1, 3]].- Why is the test
start < prev_endand not<=? In Non-overlapping Intervals (LC 435), intervals that share only an end point do not overlap.
[2, 3]and[3, 4]can both be kept. With<=, the loop removes[3, 4]and returns too large a count.- What are the time and space complexity?
O(N log N)time, because of the sort. The loop isO(N). The extra space isO(1)besides the space the sort uses. The blueprint changes the caller's list by sorting it.- How do you return the kept intervals and not only the count?
Append each kept interval to a list
keptin the loop, including the first one. The loop already decides keep or drop for each interval. The length ofkeptisn - removed_count.- What changes when each interval has a different value?
The greedy choice is no longer safe, because a short interval can have a small value and block a long one with a large value. Sort by end, then use dynamic programming: for each interval, take the best of skipping it or adding its value to the best total that ends at or before its start.
SWE Reasoning
Spot it
- The question asks for the most intervals that do not overlap, or the fewest intervals to remove so that the rest do not overlap.
- Every interval has the same value, so only the count matters.
- Choosing one interval blocks the time it covers, and the other intervals compete for the time that is left.
- The question is a scheduling one: rooms, talks, jobs, or balloons shot by one arrow.
- The answer is a count, and the chosen set itself is not needed.
The invariant, step by step
- The list is empty, so return 0. Otherwise sort
intervalsbyiv[1], which is the end time. - Keep the first interval. Set
prev_end = intervals[0][1]andremoved_count = 0. - For each
start, endin the rest of the list, teststart < prev_end. - If it is true, the interval starts before the last kept interval ends. Drop it:
removed_count += 1. - Otherwise keep it:
prev_end = end. It ends no earlier than the previousprev_end, soprev_endnever moves left. prev_endis always the end of the last kept interval, and the kept set is the largest possible among the intervals seen so far.
Traps
- Sorting by start. A long interval such as
[1, 9]comes first and blocks the short ones. For[[1, 9], [2, 3], [3, 4], [1, 3]]the loop returns 3 instead of 2. - Using
<=for the overlap test. Intervals that only touch do not overlap in Non-overlapping Intervals (LC 435).[3, 4]afterprev_end = 3must be kept. - Reading
prev_endbefore the sort.intervals[0][1]must come from the sorted list. Before the sort it is the end of an arbitrary interval. - Counting the kept intervals and returning that. The question asks for the removals. Return
removed_count, orn - kept. - Moving
prev_endon a drop. A dropped interval must not changeprev_end. Only a kept interval sets it.