会议室 I
题目
题目链接：
形容
给定一系列的会议工夫距离，包含起始和完结工夫[[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
解释:
这两个时间段不会抵触解答
/**
* 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
题目
题目链接：
形容
给定一系列的会议工夫距离 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 个会议室就够了解答
/**
* 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
题目
题目链接：
形容
你有一个以后会议列表 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]
解答
/**
* 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;
}
本篇文章如有帮忙到您，请给「翎野君」点个赞，感谢您的反对。