LeetCode Solution 435 - Non-overlapping Intervals

Problem Statement

Given an array of intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Constraints:

• 1 <= intervals.length <= 10^4
• intervals[i].length == 2
• -5 * 10^4 <= starti < endi <= 5 * 10^4

Optimal Approach

To minimize removals, we should always try to keep the interval with the smallest ending time whenever an overlap occurs. This ensures the remaining intervals have the most room to fit without overlapping.

The Greedy Algorithm is the optimal approach:

1. Sort intervals by their end time.
2. Iterate through intervals and count overlaps.
3. Remove the interval that causes an overlap (keep the one with the smaller end time).

LeetCode-Compatible C++ Solution (Greedy Approach)

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
        
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });
        
        int count = 0;
        int prevEnd = intervals[0][1];
        
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] < prevEnd) {
                count++;
            } else {
                prevEnd = intervals[i][1];
            }
        }
        return count;
    }
};

Step-by-Step Explanation of Code

1. Sort the intervals based on their end time.
2. Initialize prevEnd to track the end of the last non-overlapping interval.
3. Iterate through intervals:
   • If an interval starts before prevEnd, increment count (it must be removed).
   • Otherwise, update prevEnd.
4. Return count, representing the number of removed intervals.

Dry Run / Execution Steps

Example Input:

intervals = {{1,2}, {2,3}, {3,4}, {1,3}}

Execution Steps:

1. Sort intervals: {{1,2}, {2,3}, {3,4}, {1,3}} → {{1,2}, {1,3}, {2,3}, {3,4}}
2. Start with prevEnd = 2.
3. Compare {1,3}: Overlaps, remove it → count = 1.
4. Compare {2,3}: No overlap, update prevEnd = 3.
5. Compare {3,4}: No overlap, update prevEnd = 4.
6. Result: count = 1 (1 interval removed).

Alternative Approaches

1. Brute Force (Check all subsets)

• Generate all subsets of non-overlapping intervals and find the largest.
• Time Complexity: O(2^N)
• Space Complexity: O(N)
• Why not? Exponential time complexity, infeasible for large N.

2. Dynamic Programming (DP)

• Define dp[i] as the max number of non-overlapping intervals ending at i.
• Use binary search for optimization.
• Time Complexity: O(N log N)
• Space Complexity: O(N)
• Why not? More complex than greedy without substantial benefits.

Why Greedy is Best?

Approach	Time Complexity	Space Complexity	Feasibility
Brute Force	O(2^N)	O(N)	❌ Infeasible
DP	O(N log N)	O(N)	❌ Complex
Greedy	O(N log N)	O(1)	✅ Best Choice

Greedy is the best approach as it efficiently sorts and iterates through intervals, achieving O(N log N) time and O(1) space.

Conclusion

The Greedy Algorithm is the best choice because it ensures minimal removals while maintaining non-overlapping intervals. It sorts intervals and processes them in a single pass, making it efficient.

Similar Problems for Practice

• Meeting Rooms II (LeetCode 253)
• Minimum Number of Arrows to Burst Balloons (LeetCode 452)
• Merge Intervals (LeetCode 56)