435. Non-overlapping Intervals

📝 Problem Details

• Title: 435. Non-overlapping Intervals
• Link: https://leetcode.com/problems/non-overlapping-intervals/
• Difficulty: Medium
• Tags/Categories: Intervals

input array intervals where intervals[i] = [start,end] return the minimum number of intervals you need to remove to make the rest non-overlapping

💭What Were My Initial Thoughts?

When asked to remove the fewest number of intervals to make them non-overlapping 
- sort by end time (instead of start time)
- always keep the earliest finishing interval to leave room for others 

💡 Explanation of Solution

1. sort intervals by end time 
	- sorting by end time ensures we always keep the interval that finishes the earliest, maximising space for upcoming intervals

2. iterate through intervals
	- keep track of the end time of the last non-overlapping interval
	- if the current interval overlaps (intervals[i][0] < end), remove it and increase the count
	- otherwise, update end to the new intervals end time

3. return the count of removed intervals

⌛ Complexity Analysis

Tiem Complexity: O(n log n)
Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) {
            return a[1] < b[1]; // sort by end time
        });
 
        int end = intervals[0][1];
        int count = 0;
 
        for(int i = 1; i < intervals.size(); i++) {
            if(intervals[i][0] < end) count ++; // overlap found, remove it 
            else end = intervals[i][1]; // update end to the current interval
        }
        return count;
    }
};