253. Meeting Rooms II

Posted on | Edited on | Views:

LeetCode

Priority Queues

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;
class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int len=intervals.length;
        if(len==0) return 0;
        Arrays.sort(intervals,(a,b)->a[0]-b[0]);// Sort the intervals by start time
        PriorityQueue<Integer> q=new PriorityQueue<>();
        q.add(intervals[0][1]);// Add the first meeting
        for(int i=1;i<len;i++){
            if(intervals[i][0]>=q.peek()) q.poll();
            q.add(intervals[i][1]);
        }
        return q.size();
    }
}
/*
public class MyClass {
    public static void main(String[] args) {
        int[][] intervals={{0, 30},{5, 10},{15, 20}};
        System.out.println(new Solution().minMeetingRooms(intervals));
    }
}*/


Chronological Ordering, Greedy + Two Pointers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// O(NlogN)
public int minMeetingRooms(Interval[] intervals) {
    if (intervals == null || intervals.length == 0) return 0;
    int n = intervals.length, index = 0;
    int[] begins = new int[n];
    int[] ends = new int[n];
    for (Interval i: intervals) {
        begins[index] = i.start;
        ends[index] = i.end;
        index++;
    }
    Arrays.sort(begins);
    Arrays.sort(ends);
    int rooms = 0, pre = 0;
    for (int i = 0; i < n; i++) {
        rooms++;
        if (begins[i] >= ends[pre]) {
            rooms--;
            pre++;
        }
    }
    return rooms;
}


0%