253.Meeting-Rooms-II

253. Meeting Rooms II

题目地址

https://leetcode.com/problems/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.

Example 1:

Input: [[0, 30],[5, 10],[15, 20]]
Output: 2
Example 2:

Input: [[7,10],[2,4]]
Output: 1
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

代码

Approach 1: Priority Queue

Complexity Analysis

• Time Complexity: O_(_N_log_N).

  • There are two major portions that take up time here. One is sorting of the array that takes O_(_N_log_N) considering that the array consists of N elements.

  • Then we have the min-heap. In the worst case, all N meetings will collide with each other. In any case we have N add operations on the heap. In the worst case we will have N extract-min operations as well. Overall complexity being (NlogN) since extract-min operation on a heap takes O_(log_N).

• Space Complexity: O(_N) because we construct the min-heap and that can contain _N elements in the worst case as described above in the time complexity section. Hence, the space complexity is O_(_N).

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

  PriorityQueue<Integer> allocator = new PriorityQueue<Integer>(intervals.length, new Comparator<Integer>() {
    public int compare(Integer a, Integer b) {
      return a - b;
    }
  });

  Arrays.sort(intervals, new Comparator<int[]>() {
    public int compare(final int[] a, final int[] b) {
      return a[0] - b[0];
    }
  });

  allocator.add(intervals[0][1]);

  for (int i = 1; i < intervals.length; i++) {
    if (intervals[i][0] >= allocator.peek()) {
      allocator.poll();
    }

    allocator.add(intervals.[i][1]);
  }

  return allocator.size();
}
}

Approach #2 Chronological Ordering

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

    Integer[] start = new Integer[intervals.length];
    Integer[] end = new Integer[intervals.length];

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

    Arrays.sort(end, new Comparator<Integer>() {
      public int compare(Integer a, Integer b) {
        return a - b;
      }
    })

    Arrays.sort(start, new Comparator<Integer>() {
      public int compare(Integer a, Integer b) {
        return a - b;
      }
    });

    int startPointer = 0, endPointer = 0;

    int usedRooms = 0;
    while (startPointer < intervals.length) {
  // If there is a meeting that has ended by the time the meeting at `start_pointer` starts
      if (start[startPointer] >= end[endPointer]) {
        endPointer += 1;
      } else {
        usedRooms += 1;
      }

      startPointer +=1;
    }

    return usedRooms;
  }
}