meeting room

Meeting Rooms问题

252. Meeting Rooms

https://leetcode.com/problems/meeting-rooms/

解法一：merge interval通解

public boolean canAttendMeetings(int[][] intervals) {
    int n=intervals.length;
    if(n==0){
        return true;
    }
    Arrays.sort(intervals, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            return o1[0]!=o2[0] ? o1[0]-o2[0] : o2[0]-o1[0];
        }
    });

    int start=intervals[0][0];
    int end=intervals[0][1];
    for (int i = 1; i < n; i++) {
        int left=intervals[i][0];
        int right=intervals[i][1];
        if(left<end){
            return false;
        }else{
            end=right;
        }
    }
    return true;
}

解法二：

public boolean canAttendMeetings(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
    for (int i = 0; i < intervals.length - 1; i++) {
        if (intervals[i][1] > intervals[i + 1][0]) {
            return false;
        }
    }
    return true;
}

253. Meeting Rooms II

https://leetcode.com/problems/meeting-rooms-ii/

法一：greedy algorithm

先interval排序，尽可能让该interval去到end更小的组，并更新该组的end

public int minMeetingRooms(int[][] intervals) {
    //minimum number of conference rooms
    //minimum groups of un-overlapping intervals
    Arrays.sort(intervals,(a,b)->(a[0]!=b[0] ? a[0]-b[0] : b[1]-a[1]));
    int n=intervals.length;
    PriorityQueue<Integer> pq=new PriorityQueue();
    pq.add(intervals[0][1]);
    for (int i = 1; i < n; i++) {
        int left=intervals[i][0];
        int right=intervals[i][1];
        if(left<pq.peek()){
            pq.offer(right);
        }else{
            int min=pq.poll();
            pq.offer(right);
        }
    }
    return pq.size();
}

2402. Meeting Rooms III

注意：

• end可能越界，要用long
• compare的返回值必须是int,也要强转

public int mostBooked(int n, int[][] meetings) {
    int[] counts=new int[n];
    Arrays.sort(meetings,(a,b)->(a[0]-b[0]));
    //room number, meeting end time
    PriorityQueue<long[]> pq=new PriorityQueue<>((a,b)->(a[1]!=b[1] ? (int)(a[1]-b[1]) : (int)(a[0]-b[0])));
    pq.offer(new long[]{0,meetings[0][1]});
    counts[0]++;
    for (int i = 1; i < meetings.length; i++) {
        int start=meetings[i][0];
        int end=meetings[i][1];
        List<long[]> rooms=new ArrayList<>();
        int count=pq.size();
        long[] room=null;    //best room to offer
        while(!pq.isEmpty() && pq.peek()[1]<=start){//possible rooms to choose from
            long[] first=pq.poll();
            if(room==null || first[0]<room[0]){
                room=first;
            }
            rooms.add(first);
        }
        if(room!=null){ //no need to open a new room or wait
            room[1]=end;
            counts[(int)room[0]]++;
            for (long[] r : rooms) {
                pq.offer(r);
            }
        }else if(count<n){// still have empty rooms, no need to wait
            counts[count]++;
            pq.offer(new long[]{count,end});
        }else{  //have to wait
            room=pq.poll();
            counts[(int)room[0]]++;
            room[1]+=end-start;
            pq.offer(room);
        }
    }
    int res=0;
    int max=counts[0];
    for (int i = 1; i < counts.length; i++) {
        if(counts[i]>max){
            res=i;
            max=counts[i];
        }
    }
    return res;
}