Java O(nlogn) with heap


  • 1
    S
    public class Solution {
        public int minMeetingRooms(Interval[] intervals) {
            if(intervals==null || intervals.length==0) return 0;
            int n = intervals.length;
            Comparator<Interval> ic = new Comparator<Interval>(){
                public int compare(Interval i1, Interval i2){
                    if(i1.start==i2.start){
                        return i1.end-i2.end;
                    }
                    return i1.start - i2.start;
                }
            };
            Arrays.sort(intervals, ic);
            int count = 0;
            PriorityQueue<Integer> pq = new PriorityQueue<>();
            for(Interval i:intervals){
                if(pq.isEmpty() || pq.peek()>i.start){
                    count++;
                }else{
                    pq.poll();
                }
                pq.offer(i.end);
            }
            return count;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.