LeetCode 253. 【Java】253. Meeting Rooms II
原题链接
中等
作者:
tt2767
,
2020-03-10 15:51:43
,
所有人可见
,
阅读 1096
/**
1. 会议室尽量少, 一个会议室owner尽量多的会议, 会议区间更紧凑 -> 尽量排起点相近的会议, 接到终点最小的会议室上
2. meeting按起点排序, room 放入最小堆
如果能使用已有的会议室, 就接到已有会议的后面, 否则新开一个
*/
class Solution {
class Node{
int s, e;
public Node(int s, int e){
this.s = s;
this.e = e;
}
}
public int minMeetingRooms(int[][] intervals) {
List<Node> meetings = new ArrayList<>();
int n = intervals.length;
for (int i = 0 ; i < n ; i ++){
meetings.add(new Node(intervals[i][0], intervals[i][1]));
}
meetings.sort((a,b)->(a.s == b.s? a.e -b.e: a.s-b.s));
Queue<Node> rooms = new PriorityQueue<>((a,b)->(a.e==b.e?a.s-b.s:a.e-b.e));
for (int i = 0 ; i < n ; i++){
Node meeting = meetings.get(i);
boolean used = false;
Node room = rooms.poll();
if (room != null && meeting.s >= room.e){
room.e = meeting.e;
used = true;
}
if (!used) rooms.offer(meeting);
if (room != null) rooms.offer(room);
}
return rooms.size();
}
}