DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Non overlapping intervals

Problem

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        //same as N meetings/no. of activities
        //sort the intervals based on end time of each pair
        Queue<Pair<Integer,Integer>> q = new PriorityQueue<>((a,b)->a.getValue()-b.getValue());
        for(int i  = 0;i<intervals.length;i++){
            q.add(new Pair(intervals[i][0], intervals[i][1]));
        }
        int previousEndTime = Integer.MIN_VALUE;
        int count = 0;
        while(!q.isEmpty()){
            Pair<Integer,Integer> p  = q.remove();
            int start = p.getKey();
            int end = p.getValue();
            if(start>=previousEndTime){
                count++;
                previousEndTime = end;
            }
        }
        return intervals.length-count;

    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)