Leetcode 253 Meeting Rooms II

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.

Solution 1: Use min PQ to store the meeting rooms end time. If new meeting start time greater or equal than least element, update it. If not open a new meeting room. Report the pq size at the end. O(nlogn) complexity.

 public class Solution {  
   class CompStart implements Comparator<Interval> {  
     @Override  
     public int compare(Interval a, Interval b) {  
       return a.start-b.start;  
     }  
   }  
   public int minMeetingRooms(Interval[] intervals) {  
     int n=intervals.length;  
     Arrays.sort(intervals, new CompStart());  
     PriorityQueue<Integer> pq=new PriorityQueue<>();  
     for (int i=0; i<n; i++) {  
       if (i>0 && intervals[i].start>=pq.peek()) pq.poll();  
       pq.add(intervals[i].end);  
     }  
     return pq.size();  
   }  
 }  

Solution 2: two sorted array of start time and end time. Two pointers to iterator start array and end array. Iterate the time line, the current time active meeting is num of start minus num of end. Since need sort, still O(nlogn) solution, but fast than solution 1.

 public class Solution {  
   public int minMeetingRooms(Interval[] intervals) {  
     int n=intervals.length;  
     int[] start=new int[n];  
     int[] end=new int[n];  
     for (int i=0; i<n; i++) {  
       start[i]=intervals[i].start;  
       end[i]=intervals[i].end;  
     }  
     Arrays.sort(start);  
     Arrays.sort(end);  
     int i=0, j=0, res=0;  
     while (i<n) {  
       if (start[i]<end[j]) i++;  
       else if (start[i]>end[j]) j++;  
       else {  
         i++;  
         j++;  
       }  
       res=Math.max(res,i-j);  
     }  
     return res;  
   }  
 }