Java - greedy algorithm with priority queue


  • 4
    J
       public int minMeetingRooms(Interval[] intervals) {
        if (intervals == null || intervals.length == 0)
            return 0;
            
    	Comparator<Interval> comp = new Comparator<Interval>() {
    		@Override
    		public int compare(Interval o1, Interval o2) {
     			return o1.start - o2.start;
    		}
    	};
    	Arrays.sort(intervals, comp);
    	
    	PriorityQueue<Interval> queue = new PriorityQueue<Interval>(intervals.length, new Comparator<Interval>() {
    		@Override
    		public int compare(Interval o1, Interval o2) {
    			return o1.end - o2.end;
    		}
    	}
    	);
    	
    	for (int i = 0; i < intervals.length; i++) {
    		if (queue.isEmpty()) {
    			queue.offer(intervals[i]); //start the first meeting in a new room.
    		} else {
    			Interval finishingMeeting = queue.poll(); // get the previous meeting with earliest finishing time.
    			if (intervals[i].start < finishingMeeting.end) {
    				queue.offer(intervals[i]); //the meeting isn't finished yet, start meeting in a new room.
    			} else {
    				finishingMeeting.end = intervals[i].end; // using the room by the previous meeting.
    			}
    			queue.offer(finishingMeeting);
    		}
    
    	}
    	return queue.size();  
    }

Log in to reply
 

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