会议室I
题目
题目链接：https://www.lintcode.com/problem/920
代码语言：javascript复制描述
给定一系列的会议时间间隔，包括起始和结束时间[[s1,e1]，[s2,e2]，…(si < ei)，确定一个人是否可以参加所有会议。
样例1
输入: intervals = [(0,30),(5,10),(15,20)]
输出: false
解释:
(0,30), (5,10) 和 (0,30),(15,20) 这两对会议会冲突
样例2
输入: intervals = [(5,8),(9,15)]
输出: true
解释:
这两个时间段不会冲突解答
代码语言：javascript复制/**
* 920
* 给定一系列的会议时间间隔，包括起始和结束时间[[s1,e1]，[s2,e2]，…(si < ei)，确定一个人是否可以参加所有会议。
*
* @param intervals: an array of meeting time intervals
* @return: if a person could attend all meetings
*/
public boolean canAttendMeetings(List<Interval> intervals) {
if (intervals == null || intervals.size() == 0) {
return true;
}
Collections.sort(intervals, new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
return o1.start - o2.start;
}
});
int end = intervals.get(0).getEnd();
for (int i = 1; i < intervals.size(); i ) {
if (intervals.get(i).getStart() < end) {
return false;
}
// 1,7 8,10
//end = Math.max(end, intervals.get(i).getEnd());
end = intervals.get(i).getEnd();
}
return true;
}会议室II
题目
题目链接：https://www.lintcode.com/problem/919/
代码语言：javascript复制描述
给定一系列的会议时间间隔intervals，包括起始和结束时间[[s1,e1],[s2,e2],...] (si < ei)，找到所需的最小的会议室数量。
样例1
输入: intervals = [(0,30),(5,10),(15,20)]
输出: 2
解释:
需要两个会议室
会议室1:(0,30)
会议室2:(5,10),(15,20)
样例2
输入: intervals = [(2,7)]
输出: 1
解释:
只需要1个会议室就够了解答
代码语言：javascript复制/**
* 919
* 给定一系列的会议时间间隔intervals，包括起始和结束时间[[s1,e1],[s2,e2],...] (si < ei)，
* 找到所需的最小的会议室数量。
*
* @param intervals: an array of meeting time intervals
* @return: the minimum number of conference rooms required
*/
public int minMeetingRooms(List<Interval> intervals) {
if (intervals == null || intervals.size() == 0) {
return 0;
}
Collections.sort(intervals, new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
return o1.start - o2.start;
}
});
PriorityQueue<Integer> endTimeList = new PriorityQueue<>();
endTimeList.offer(intervals.get(0).getEnd());
for (int i = 1; i < intervals.size(); i ) {
if (intervals.get(i).getStart() >= endTimeList.peek()) {
endTimeList.poll();
}
endTimeList.offer(intervals.get(i).getEnd());
}
return endTimeList.size();
}会议室III
题目
题目链接：https://www.lintcode.com/problem/1897/
代码语言：javascript复制描述
你有一个当前会议列表intervals，里面表明了每个会议的开始和结束时间，以及一些会议室rooms。现在有一系列会议ask需要加入，逐个判断他们能否被安排进当前的会议列表中而不产生冲突。一个会议室在同一时间只能进行一场会议。每个询问都相互独立。
被安排的会议可以拆分。如果需要安排一个[2, 4]的会议，你可以把它分成[2, 3]和[3, 4]两段来进行。
例 1:
输入:
Intervals:[[1,2],[4,5],[8,10]],rooms = 1,ask: [[2,3],[3,4]]
输出:
[true,true]
解释:
对于[2,3]的询问，我们可以安排一个会议室room0。
以下是room0的会议列表：
[[1,2],[2,3],[4,5],[8,10]]
对于[3,4]的询问，我们可以安排一个会议室room0。
以下是room0的会议列表：
[[1,2],[3,4],[4,5],[8,10]]
例 2:
输入:
[[1,2],[4,5],[8,10]]
1
[[4,5],[5,6]]
输出:
[false,true]解答
代码语言：javascript复制/**
* 1897
* 你有一个当前会议列表intervals，里面表明了每个会议的开始和结束时间，以及一些会议室rooms。现在有一系列会议ask需要加入，逐个判断他们能否被安排进当前的会议列表中而不产生冲突。一个会议室在同一时间只能进行一场会议。每个询问都相互独立。
* <p>
* 被安排的会议可以拆分。如果需要安排一个[2, 4]的会议，你可以把它分成[2, 3]和[3, 4]两段来进行。
*
* @param intervals: the intervals
* @param rooms: the sum of rooms
* @param ask: the ask
* @return: true or false of each meeting
*/
public boolean[] meetingRoomIII(int[][] intervals, int rooms, int[][] ask) {
// 1.汇总统计每个会议的开始时间和结束时间对应的数量
Map<Integer, Integer> sumMap = new HashMap<>();
for (int[] interval : intervals) {
sumMap.put(interval[0], sumMap.getOrDefault(interval[0], 0) 1);
sumMap.put(interval[1], sumMap.getOrDefault(interval[1], 0) - 1);
}
// 2.将开始结束时间归并到同一个列表中
List<int[]> originalList = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry : sumMap.entrySet()) {
originalList.add(new int[]{entry.getKey(), entry.getValue()});
}
// 3.列表中的时间按先后顺序排序
Collections.sort(originalList, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
int preNum = 0;
List<int[]> invalidList = new ArrayList<>();
// 4.当前时间段内还能否再被插入新的会议
for (int i = 0; i < originalList.size(); i ) {
int[] v = originalList.get(i);
preNum = v[1];
// 当前时间点内的会议室全部被占满了
if (preNum == rooms) {
// 被安排的会议可以拆分。如果需要安排一个[2, 4]的会议，你可以把它分成[2, 3]和[3, 4]两段来进行。
// 以最小单位放入
invalidList.add(new int[]{v[0], originalList.get(i 1)[0]});
}
}
// 5.构建返回结果
boolean[] ans = new boolean[ask.length];
if (invalidList.size() == 0) {
Arrays.fill(ans, true);
return ans;
}
for (int i = 0; i < ask.length; i ) {
// 寻找到 invalidList.get(i)[1] 大于 ask[i][0]
// 在无效会议区间中找到一个结束时间，比，当前要加入的会议的开始时间，要大的位置
// 这段无效不能加入的区间还没结束，你却想加入进来
int index = helper(invalidList, ask[i]);
// |________|
//
if (index != invalidList.size() && invalidList.get(index)[0] < ask[i][1]) {
// 当前无效的不能加入的会议时间区间开始时间 < 请求加入的会议室的结束时间
ans[i] = false;
} else if (index != 0 && invalidList.get(index - 1)[1] > ask[i][0]) {
ans[i] = false;
} else {
ans[i] = true;
}
}
return ans;
}
/**
* 使用二分查找 寻找到 pos.get(i)[1] 大于 one[0]
*
* @param pos
* @param one
* @return
*/
public int helper(List<int[]> pos, int[] one) {
int left = 0;
int right = pos.size() - 1;
while (left <= right) {
int mid = (left right) >> 1;
if (pos.get(mid)[1] > one[0]) {
right = mid - 1;
} else {
left = mid 1;
}
}
return left;
}首发链接：https://cloud.tencent.com/developer/article/2285726
