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.

&nbsp;
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.


&nbsp;
Constraints:


	1 &lt;= intervals.length &lt;= 105
	intervals[i].length == 2
	-5 * 104 &lt;= starti &lt; endi &lt;= 5 * 104


class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: # Time: O(nlogn) and Space: O(1)
        intervals.sort()
        res = 0
        prevEnd = intervals[0][1]

        for start, end in intervals[1:]: # we will start from 1 as we already had taken 0 as a base value
            if start >= prevEnd: # Non overlapping when new interval starts after or from the previous one
                prevEnd = end # prev = [2, prevEnd=3] & new = [start=3, end=4], we have a new end now after checking the new non overlapping interval
            else: # Overlapping when new interval starts in between or from the previous one
                res += 1 # prev = [1, prevEnd=2] & new = [start=1, end=3] --> we will delete new=[1, 3] & set prev = [1, prevEnd=2]
                prevEnd = min(end, prevEnd) # we will delete on the interval on the basis of whose interval ends last

        return res
// |-------|
//   |--|

// |-------|
//.   |-------|

// |-------|
//.           |-------|

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a,b) -> a[0] - b[0]);
        
        int start = intervals[0][0];
        int end = intervals[0][1];
        int res = 0;
        
        for (int i = 1; i < intervals.length; i++){
            int[] interval = intervals[i];
            
            if(interval[0] >= start && interval[0] < end){
                res++;
                if (interval[1] >= end)
                    continue;
            }
            start = interval[0];
            end = interval[1];
    }
        
        return res;
    }
}
class Solution {
        void solve(priority_queue <pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> &pq,int e,int &cnt){

       while(!pq.empty() && pq.top().first<e){
           e = min(e,pq.top().second);
             pq.pop();
             cnt++;
        }
       
    }

public:
    int eraseOverlapIntervals(vector<vector<int>>& grid) {
           priority_queue <pair<int,int>, 
           vector<pair<int,int>>, greater<pair<int,int>> > pq;

       for(int i =0; i<grid.size(); i++){
           pq.push({grid[i][0],grid[i][1]});
       }
       int cnt =0;
       while(!pq.empty()){
           int e = pq.top().second;
           pq.pop();
           solve(pq,e,cnt);
       }
       return cnt;
    }
};
var eraseOverlapIntervals = function(intervals) {
    // sort by end's small to big
    intervals.sort((a, b) => a[1] - b[1]);
    
    let total = 1;
    let maxEnd = intervals[0][1];
    
    for (let i = 1; i < intervals.length; i++) {
        let [start, end] = intervals[i];
        if (start >= maxEnd) {
            total++;
            maxEnd = end
        }
    }
    
    return intervals.length - total;
};
Non-overlapping Intervals