AC Java solution using min heap


  • 153

    Just want to share another idea that uses min heap, average time complexity is O(nlogn).

    public int minMeetingRooms(Interval[] intervals) {
        if (intervals == null || intervals.length == 0)
            return 0;
            
        // Sort the intervals by start time
        Arrays.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval a, Interval b) { return a.start - b.start; }
        });
        
        // Use a min heap to track the minimum end time of merged intervals
        PriorityQueue<Interval> heap = new PriorityQueue<Interval>(intervals.length, new Comparator<Interval>() {
            public int compare(Interval a, Interval b) { return a.end - b.end; }
        });
        
        // start with the first meeting, put it to a meeting room
        heap.offer(intervals[0]);
        
        for (int i = 1; i < intervals.length; i++) {
            // get the meeting room that finishes earliest
            Interval interval = heap.poll();
            
            if (intervals[i].start >= interval.end) {
                // if the current meeting starts right after 
                // there's no need for a new room, merge the interval
                interval.end = intervals[i].end;
            } else {
                // otherwise, this meeting needs a new room
                heap.offer(intervals[i]);
            }
            
            // don't forget to put the meeting room back
            heap.offer(interval);
        }
        
        return heap.size();
    }

  • 3
    C

    If there is room conflict, add both meeting time slots back. If there is no conflict, just add the new one.
    for (int i = 1; i<intervals.length; i++) {
    Interval top = minHeap.poll();
    if (intervals[i].start<top.end) {
    minHeap.offer(top);
    }
    minHeap.offer(intervals[i]);
    }


  • 6
    B

    Why greedy works for this problem, can anyone explain or give some hints? Thanks!


  • 48
    C

    A different version of code with similar thought. Every time the new interval start is larger than the minimum end, pop the interval in the queue. In addition, really enjoy the java 8 lambda style comparator : )

    public class Solution {
        public int minMeetingRooms(Interval[] intervals) {
            if(intervals == null || intervals.length == 0) return 0;
            Arrays.sort(intervals, (a, b) -> (a.start - b.start));
            int max = 0;
            PriorityQueue<Interval> queue = new PriorityQueue<>(intervals.length, (a, b) -> (a.end - b.end));
            for(int i = 0; i < intervals.length; i++){
                while(!queue.isEmpty() && intervals[i].start >= queue.peek().end)
                    queue.poll();
                queue.offer(intervals[i]);
                max = Math.max(max, queue.size());
            }
            return max;
        }
    }

  • 0
    L

    Great Solution.

    I think we could simply return the size of heap. Because every time we don't have a conflict, we just poll out one room.

    BTW, awesome sort.
    how you come up (a, b) -> (a.start - b.start)?


  • 0
    W

    similar with you, here's my cpp solution :)

    class Solution {
    public:
        static bool cmp(Interval a,Interval b)
        {
            return a.start<=b.start;
        }
        
        int minMeetingRooms(vector<Interval>& intervals) {
        if(intervals.empty()) return 0;
        sort(intervals.begin(),intervals.end(),cmp);
        int maxroom=1;
        priority_queue<int> endtime;
        for(auto i:intervals)
        {
            while(!endtime.empty()&&i.start>=(-endtime.top()))
            {
                endtime.pop();
            }
            endtime.push(-i.end);  //max_heap in cpp
            maxroom=max(maxroom,(int)endtime.size());   
        }
        return maxroom;
        }
    };

  • 0

    Good job! :)


  • -1

    Even I would like to know answer for @bihuzhua's question.


  • 0
    D
    This post is deleted!

  • 9
    D

    can be more simple

    public int minMeetingRooms(Interval[] intervals) {
    	if (intervals.length == 0) {
    		return 0;
    	}
    	// sort
    	Arrays.sort(intervals, new Comparator<Interval>() {
    		@Override
    		public int compare(Interval a, Interval b) {
    			return a.start - b.start;
    		}
    	});
    	// PriorityQueue
    	PriorityQueue<Integer> ends = new PriorityQueue<Integer>();
    	ends.offer(intervals[0].end);
    	for (int i = 1; i < intervals.length; i++) {
    		if (intervals[i].start >= ends.peek()) { // no overlap, then should update smallest end.
    			ends.poll();
    		} 
    		ends.offer(intervals[i].end);
    	}
    	return ends.size();
    }

  • 0
    L

    i am confused why the time complexity is nlogn


  • 0
    G

    You can also replace the regular "for" with for-each, so the code will be a bit clearer.


  • 1
    B

    very clear explanation. great!


  • 0
    M

    This is so clever, lol!


  • 0
    C

    Question on the solution: what's the purpose of max? Why it's not necessarily the final queue size?


  • 1
    H

    Max tracks the maximum number of rooms that were required at any one time.The final queue size will be reduced for each reservation that doesn't have a conflict. Suppose at one time, 3 rooms were required, then just because there are 3 reservations without conflict, the final queue size would reduce to zero. Zero is incorrect.


  • 0
    G
    This post is deleted!

  • 29
    D

    @jeantimex Excellent solution!

    If you look at these events in a time line one after another (like stream data), then this solution is a greedy solution.

    The heap stores all conflicting events, which must be resolved by independent rooms. The heap's head is the event that has earliest end/finish time. All other events collide with each other mutually in the heap.

    When a new event comes (this is the reason that we need to sort by event.start), we greedily choose the event A that finished the earliest (this is the reason that we use minheap on end time). If the new event does not collide with A, then the new event can re-use A's room, or simply extend A's room to the new event's end time.

    If the new event collides with A, then it must collide with all events in the heap. So a new room must be created.

    The reason for correctness is the invariant: heap size is always the minimum number of rooms we need so far. If the new event collides with everyone, then a new room must be created; if the new event does not collide with someone, then it must not collide with the earliest finish one, so greedily choose that one and re-use that room. So the invariant is maintained.

    I wish I can have this thinking angle :)


  • 0
    This post is deleted!

  • 0

    Here is the real CPP copy of the alg.

    struct cmpInPq{
        bool operator()(Interval& a, Interval& b) {
            return a.end >= b.end;
        }
    };
    
    class Solution {
    public:
        int minMeetingRooms(vector<Interval>& intervals) {
            if (intervals.empty()) return 0;
    
            sort(intervals.begin(), intervals.end(), [](Interval& a, Interval& b){ return a.start < b.start;});
    
            priority_queue<Interval, vector<Interval>, cmpInPq> pq;
    
            pq.push(intervals[0]);
    
            for (int i = 1; i < intervals.size(); i++) {
                Interval top = pq.top();
                pq.pop();
                if (intervals[i].start >= top.end) {
                    top.end = intervals[i].end;
                } else {
                    pq.push(intervals[i]);
                }
                pq.push(top);
            }
            return pq.size();
        }
    };
    

Log in to reply
 

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