> For the complete documentation index, see [llms.txt](https://wentao-shao.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wentao-shao.gitbook.io/leetcode/data-structure/253.meeting-rooms-ii.md).

# 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 (*N**l**o**g**N*) since extract-min operation on a heap takes O\_(log\_N).
* Space Complexity: &#x4F;*(\_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).

```java
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

```java
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;
  }
}
```