Java solution using priority queue


  • 0
    Y

    '''
    public class Solution {
    public int minMeetingRooms(Interval[] intervals) {
    if(intervals==null||intervals.length==0)
    {
    return 0;
    }

        Arrays.sort(intervals,new IntervalComparator());
        PriorityQueue<Interval> heap = new PriorityQueue<Interval>(intervals.length,new Comparator<Interval>(){
            public int compare(Interval a, Interval b){return a.end-b.end;}
            });
        heap.offer(intervals[0]);
    
        for(int i=1; i<intervals.length;i++)
        {
             Interval interval=heap.poll();
             //you can have an equal here.
             if(intervals[i].start>=interval.end)
             {
                interval.end=intervals[i].end;
             }
             else
             {
             	heap.offer(intervals[i]);
             }
             heap.offer(interval);
        }
    
        return heap.size();
    
       
       
    }
    
    public class IntervalComparator implements Comparator <Interval>{
     
         public int compare(Interval a, Interval b)
         {
         	if(a.start<b.start)
         		return -1;
         	else if(a.start>b.start)
         		return 1;
         	else 
         		return 0;
         }
    }
    

    }


  • 0
    Y

    The idea is just each to maintain a mean heap and each time you just want to see if the meeting with the smallest ending time is less than the curr start meeting time or not, if it is it means the current meeting can use the same room as the one with the smallest end time.


Log in to reply
 

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