Non-overlapping Intervals

Given a collection of intervals, find the minimum number of intervals

you need to remove to make the rest of the intervals non-overlapping.

Example 1:

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

Output: 1

Explanation: [1,3] can be removed and the rest of intervals are

non-overlapping.

Logic

Sort array's elements by their end and delete sorted elements whose start are less than previous one's end.

Time Complexity

O(n)

Space Complexity

O(n)

Code

public class Solution {    public int eraseOverlapIntervals(Interval[] intervals) {        if (intervals.length == 0)            return 0;        PriorityQueue
    
      pq = new PriorityQueue
     
      (10, new MyComparator());        for(Interval it: intervals)            pq.add(it);                        int endpoint = 0;        int count = 0;        while(pq.size()>1){            endpoint = pq.poll().end;            while(pq.size()>0&&pq.peek().start
      
       {        public int compare(Interval a, Interval b){                        return a.end - b.end;        }                    }}