Non-overlapping intervals (#435 Leetcode)

 Given an array of intervals 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.

 

Example 1:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

Example 2:

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.

Example 3:

Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

 

Constraints:

• 1 <= intervals.length <= 105
• intervals[i].length == 2
• -5 * 104 <= starti < endi <= 5 * 104

We need to remove a few of the intervals to maximise the non-overlapping intervals. If it is not sorted, we need to compare each interval with other intervals which is O(N^2). 

So, let's sort first. But, do we need to sort based on start time or finish time. Let's research. 

1. Sort based on start time (Earliest starting Time)

Example: [[1, 2], [2, 3], [1, 3], [3, 4]]

Output: [[1, 2], [2, 3],  [3, 4]] 

Solution : 

After sorting [[1, 2], [1, 3],  [2, 3], [3, 4]].

If two intervals' start time is same, remove the second interval [1, 3] as both intervals have the same start time. The output would be  [[1, 2], [2, 3],  [3, 4]] 

Counter Example: [ [2, 3], [1, 6], [1, 2], [3, 4]]

Output: [[1, 2], [2, 3],  [3, 4]] 

Solution : 

After sorting [[1, 6], [1, 2],  [2, 3], [3, 4]].

Remove  [1, 2] as both intervals have the same start time. The output would be  [[1, 6], [2, 3],  [3, 4]] but this is overlapping intervals. 

2. Sort based on finish time (Earliest Finishing Time)

Example: [ [2, 3], [1, 6], [1, 2], [3, 4]]

Output: [[1, 2], [2, 3],  [3, 4]] 

Solution : 

After sorting [[1, 2],  [2, 3], [3, 4], [1, 6]].

If the previous intervals finish time is greater than next interval's start time, remove  next interval [1, 6] as it will overlap. The output would be  [[1, 2], [2, 3],  [3, 4]] and this is the optimal solution. 

bool sortFinish(vector<int>& a, vector<int>& b) {
        return a[1] < b[1];
    }
class Solution {
    
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int n = intervals.size();
        
        if (n <= 0 || n > 100000) {
            return 0;
        }
        
        for (int i = 0; i < n; i++) {
            if (intervals[i].size() > 2) {
                return 0;
            }
        }
        sort(intervals.begin(), intervals.end(), sortFinish);
        
        #if 0
        cout << "After sorting\n ";
        for (int i = 0; i < n; i++) {
           cout << "\nstart " << intervals[i][0] << " finish " << intervals[i][1] << endl;
        }
        #endif
        
        int minRemove = 0;
        vector<int> prev = intervals[0];
        
        for (int i = 1; i < n; i++) {
            if (prev[1] > intervals[i][0]) {
                minRemove++;
            } else {
                prev = intervals[i];
                
            }
        }
        return minRemove;
    }
};