JAVA solution with PriorityQueue<Integer>


  • 0
    T
    /**
     * Definition for an interval.
     * public class Interval {
     *     int start;
     *     int end;
     *     Interval() { start = 0; end = 0; }
     *     Interval(int s, int e) { start = s; end = e; }
     * }
     */
    
    //the question asks to find the max no. of meetings occurring simultaneously. O(n^2)
    class Solution {
        public int minMeetingRooms(Interval[] intervals) {
            Arrays.sort(intervals, new Comparator<Interval>(){
                @Override
                public int compare(Interval I1, Interval I2){
                    return I1.start - I2.start;
                }
            });
            
            int max = 0;
            for(int i = 0; i < intervals.length; i++){
                int tempNo = 0;
                
                //use a heap to store all the intervals' end time whose value is smaller than intervals[i].end.
                //B/c it is possible for some intervals who start after intervals[i] but end before intervals[i].
                //We need to free the conference room for those intervals before iterate the next ones.
                PriorityQueue<Integer> pq = new PriorityQueue<>();
                for(int j = i; j < intervals.length; j++){
                    if(intervals[j].start<intervals[i].end){
                        if(intervals[j].end<intervals[i].end){
                            pq.add(intervals[j].end);
                        }
                        while(!pq.isEmpty() && pq.peek() <= intervals[j].start){
                            tempNo -= 1;
                            pq.poll();
                        }
                        tempNo += 1;
                        max = Math.max(max, tempNo);
                    }
                    else{
                        break;
                    }
                }
                
            }
            
            return max;
        }
    }
    

Log in to reply
 

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