关于区间集合:
这个问题的难点在于如何有效地处理会议的冲突。具体来说,需要在每个时间点追踪哪些会议正在进行,然后决定是否需要额外的会议室。下面是一些思考的建议和线索:
排序:这是一个重要的线索。当你看到这种需要比较或者组织时间区间的问题时,排序通常是一个有用的第一步。在本问题中,按照开始时间对会议进行排序可以帮助我们逐个地处理会议,确保我们先处理开始时间早的会议。 优先队列(最小堆):在处理一系列事件,其中每个事件都有开始和结束时间,并且可能会发生冲突的情况下,优先队列(特别是最小堆)经常会被用到。在本问题中,我们需要知道当前正在进行的所有会议中最早结束的那一个,以决定是否需要一个新的会议室。最小堆正好可以提供这个功能,因为它总是把最小的元素放在前面。 贪心思想:这是一个隐藏的线索。这个问题可以通过一种贪心的方式来解决,即总是尽可能地复用会议室。具体来说,每次当一个新的会议开始时,如果有一个会议已经结束,那么我们就可以在同一个会议室举行这个新的会议,而不需要新开一个会议室。这个策略保证了我们总是使用最少数量的会议室。 重叠区间问题:类似的问题经常出现在算法问题中,所以可以作为一个模式来识别。当你看到需要处理重叠区间的问题时,可以想到使用排序和优先队列来解决。 在碰到这类问题时,练习和经验也很重要。一开始可能不容易看出解决方案,但通过解决更多的类似问题,你将能够更容易地识别出相应的模式,并找到正确的方法来解决这类问题。
253. Meeting Rooms II
Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.
Example 1:
Input: intervals = [[0,30],[5,10],[15,20]] Output: 2
Example 2:
Input: intervals = [[7,10],[2,4]] Output: 1
Constraints:
1 <= intervals.length <= 104 0 <= starti < endi <= 106 class Solution { public int minMeetingRooms(int[][] intervals) { Arrays.sort(intervals, (a, b)->Integer.compare(a[0], b[0])); PriorityQueue<Integer> heap = new PriorityQueue<>(); heap.add(intervals[0][1]); int res = 1; for(int i = 1;i<intervals.length;i++){ if(intervals[i][0]>=heap.peek()){ heap.poll(); }else{ res++; } heap.add(intervals[i][1]); } return res; } } 这段代码的主要结构和组成:
...