Gyh's Braindump

253. Meeting Rooms II

tags
PriorityQueue, two pointers
source
leetcode

Edge Cases

Solution 1 - PriorityQueue

  1. sort by start time
  2. push interval’s endtime into pq, everytime peek pq if no available room, push into pq
class Solution {
    public int minMeetingRooms(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
           public int compare(int[] i1, int[] i2) {
               return i1[0] - i2[0];
           }
        });
        PriorityQueue<Integer> pq = new PriorityQueue();

        for (int[] interval: intervals) {
            int start = interval[0], end = interval[1];
            if (pq.size() == 0 || pq.peek() > start) {
                pq.add(end);
            } else {
                pq.poll();
                pq.add(end);
            }
        }

        return pq.size();
    }
}

Complexity

  • time: O(NlgN) sort O(NlgN) + each element 2O(NlgN) = 3O(NlgN)
  • space: O(N)

Solution 2

  1. sort start time into start[]
  2. sort end time into end[]
  3. two pointers, each time sp add 1, used add 1 and in the meantime, if start[sp] >= end[sp], means a room becomes available, used minus 1
class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int[] start = new int[intervals.length];
        int[] end = new int[intervals.length];

        for (int i = 0; i < intervals.length; i++) {
            start[i] = intervals[i][0];
            end[i] = intervals[i][1];
        }

        Arrays.sort(start);
        Arrays.sort(end);

        int used = 0;
        int sp = 0, ep = 0;
        while (sp < start.length) {
            if (start[sp] >= end[ep]) { // no room available
                used--;
                ep++;
            }
            used++;
            sp++;
        }

        return used;
    }
}

Complexity

  • time: O(NlgN) sort: 2O(NlgN) + build start, end O(N) + each element O(N) = 2O(NlgN) + 2O(N)
  • space: O(N)