sorting/heap-sort/meeting-rooms-ii

Meeting Rooms II

描述

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (s_i < e_i), 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

分析

首先将数组按照interval的开始时间排序，然后设置一个小根堆，用于存储的正在使用中的会议室，按结束时间排序，堆顶就是结束时间最小的interval。遍历数组，把一个一个的interval压入堆，每次压入之前，把新区间与堆顶的区间进行比较，如果新区间的开始时间大于堆顶的结束时间，说明堆顶的会议室已经结束，把它弹出，然后压入新区间。数组遍历结束后，堆的大小就是所需要的会议室数量。

// Meeting Rooms II
// Time Complexity: O(nlogn), Space Complexity: O(n)
class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals.length == 0) return 0;
        Arrays.sort(intervals,(int[] a, int[] b) ->a[0] - b[0]);

        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        pq.offer(intervals[0][1]);

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

        return pq.size();
      }
}

// TODO

相关题目

• Meeting Rooms