If two intervals end at the exact same time, does the order matter?

No, the order does not matter in that specific edge case. If you have [1, 5] and [2, 5], keeping either one still results in an ending boundary of 5, meaning the remaining free space for future intervals is perfectly identical regardless of which one the sorting algorithm places first.

How do we determine if two intervals overlap?

Two intervals $[a, b]$ and $[c, d]$ (where $a \le c$) overlap if $c < b$. If the start time of the second interval is strictly less than the end time of the first interval, they conflict and cannot coexist.

If two intervals touch at the endpoint (e.g., [1, 2] and [2, 3]), is that considered an overlap?

No, touching at boundaries is explicitly allowed in this problem. An interval ending at time $2$ finishes right as the next interval starts at time $2$, so no overlap occurs.

Non-overlapping Intervals: Minimum Removals

Q: Why do we sort by the end time instead of the start time?

If you sort by start time, you run the risk of accepting an interval that starts early but spans a massive amount of time, like [1, 100]. This massive interval would force you to delete dozens of smaller valid intervals like [2, 3], [4, 5], etc. Sorting by the end time explicitly guarantees that we are leaving the maximum possible free space available on the right side of the timeline for future intervals to be safely accommodated.

Q: If two intervals touch at the endpoint (e.g., [1, 2] and [2, 3]), is that considered an overlap?

No, touching at boundaries is explicitly allowed in this problem. An interval ending at time $2$ finishes right as the next interval starts at time $2$, so no overlap occurs.

Given an array of intervals where each interval is represented by a start time and an end time. Find the minimum number of intervals you need to remove to make the rest of the intervals strictly non-overlapping. Note that intervals that only touch at the boundaries (for example, [1, 2] and [2, 3]) are not considered overlapping.

Example 1

Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]

Output: 1

Explanation: The interval [1, 3] overlaps with both [1, 2] and [2, 3]. By removing just the single interval [1, 3], the remaining schedule [[1, 2], [2, 3], [3, 4]] is perfectly conflict-free.

Example 2

Input: intervals = [[1, 2], [1, 2], [1, 2]]

Output: 2

Explanation: All three intervals occupy the exact same span of time. You must pick one to keep and remove the other two.

Practice it by yourself before moving onto the solutionTry now

Approach

The goal is to keep as many non-overlapping intervals as possible. If two candidate intervals are available, keeping the one that ends earlier is safer because it blocks less future time.

Sorting by end time makes this greedy choice direct. The first interval is kept. After that, each interval is compared with the end time of the last kept interval. If its start time is smaller than that end time, it overlaps and must be removed. Otherwise, it can be kept, and the last kept end time is updated.

This works because every kept interval ends as early as possible among the remaining choices, so future intervals get the best chance to fit.

Algorithm

Return 0 immediately when the interval list is empty.
Sort intervals by their end time in ascending order.
Keep the first interval and store its end time as the current boundary.
Traverse the remaining intervals in sorted order.
If the current interval starts before the stored end time, count it as removed.
Otherwise, keep it and update the stored end time; return the final removal count.

Dry Run

Non Overlapping Intervals Dry Run

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4class Solution {
5public:
6    // Orders intervals by smaller end time first.
7    static bool comp(vector<int>& first, vector<int>& second) {
8        return first[1] < second[1];
9    }
10
11    // Returns the minimum number of intervals to remove.
12    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
13        // Empty input has no overlapping interval to remove.
14        if (intervals.empty()) {
15            return 0;
16        }
17
18        // Sort intervals so the interval ending earliest is considered first.
19        sort(intervals.begin(), intervals.end(), comp);
20
21        int removeCount = 0;
22        int lastEndTime = intervals[0][1];
23
24        // Check every remaining interval against the last kept interval.
25        for (int i = 1; i < intervals.size(); i++) {
26            // A start before the last kept end time means the current interval overlaps.
27            if (intervals[i][0] < lastEndTime) {
28                removeCount++;
29            // A start at or after the last kept end time means the interval can stay.
30            } else {
31                lastEndTime = intervals[i][1];
32            }
33        }
34
35        return removeCount;
36    }
37};
38
39// Driver code
40int main() {
41    vector<vector<int>> intervals = {{1, 2}, {2, 3}, {3, 4}, {1, 3}, {2, 4}, {4, 5}};
42
43    // instance for class Solution
44    Solution sol;
45
46    cout << sol.eraseOverlapIntervals(intervals) << '\n';
47    return 0;
48}

Complexity Analysis

Time Complexity: O(N log N). The absolute bottleneck of this algorithm is sorting the intervals based on their end times. The loop itself only visits each interval once, meaning it operates in linear O(N) time, but the overall time complexity is constrained by the initial sorting process.

Space Complexity: O(1). We strictly use a couple of integer variables to track the end time and the removal count. Note that some built-in language sorting functions may secretly use O(log N) auxiliary stack space beneath the hood, but no dynamic data structures are allocated.

Interview follow-up Questions