题目大意：
安排会议日程
你是一名行政助理，手里有两位客户的空闲时间表：slots1 和 slots2，以及会议的预计持续时间 duration，请你为他们安排合适的会议时间。
「会议时间」是两位客户都有空参加，并且持续时间能够满足预计时间 duration 的 最早的时间间隔。
如果没有满足要求的会议时间，就请返回一个 空数组。
「空闲时间」的格式是 [start, end]，由开始时间 start 和结束时间 end 组成，表示从 start 开始，到 end 结束。
题目保证数据有效：同一个人的空闲时间不会出现交叠的情况，也就是说，对于同一个人的两个空闲时间 [start1, end1] 和 [start2, end2]，要么 start1 > end2，要么 start2 > end1。
示例 1：
输入： slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8 输出：[60,68]
示例 2：
输入： slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 12 输出：[]
提示：
- 1 <= slots1.length, slots2.length <= 10^4
- slots1[i].length, slots2[i].length == 2
- slots1[i][0] < slots1[i][1]
- slots2[i][0] < slots2[i][1]
- 0 <= slots1[i][j], slots2[i][j] <= 10^9
- 1 <= duration <= 10^6
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1229
解题思路分析：
解这道题目之前应该先对两个数组按照起始时间进行升序排序。排序后，从两个数组的第0位开始比较，比较结果会有以下几种情况：
- 客户1与客户2的空闲时间区间为包含关系时，子集部分为两者共同空闲时间，如果子集的时间长度大于等于duration，那么子集的开始时刻到加上duration的区间为解，反之，子集所代表的的一方index加一，继续比较。
- 客户1与客户2的空闲时间区间是部分交集关系，那么要看交集的部分是否大于等于duration，如果是，那么交集的起点到加上duration的区间为解，如果否，结束时间较早的一方index加一，继续比较。
- 当客户1与客户2的空闲时间区间没有交集时，结束时间较早的一方index加一，继续比较。
当循环结束后，没有在上述三种三种情况中找到解，返回空List即可。
实现代码：
public List<Integer> minAvailableDuration(int[][] slots1, int[][] slots2, int duration) {
Comparator c = new Comparator<int[]>() { // 按照开始时间排序
@Override
public int compare(int[] o1, int[] o2) {
return o1[0]-o2[0];
}
};
Arrays.sort(slots1, c); // 排序slots1
Arrays.sort(slots2, c); // 排序slots2
int i1=0, i2=0; // 起始时，客户1和客户2的下标均为0
while(i1<slots1.length && i2<slots2.length){
// 客户1的结束时间小于客户2的开始时间，两者不相交
if(slots1[i1][1]<slots2[i2][0]){
i1++; // 客户1的index加一
}
// 客户2的结束时间小于客户1的开始时间，两者不相交
else if(slots2[i2][1]<slots1[i1][0]){
i2++; // 客户2的index加一
}
// 客户2是客户1的子集
else if(slots1[i1][0]<=slots2[i2][0]
&&slots1[i1][1]>=slots2[i2][1]){
// 当客户2的时间区间长度大于等于duration
if(slots2[i2][1]-slots2[i2][0]>=duration){
// 返回合理区间
return getList(slots2[i2][0], duration);
}
i2++; // 客户2的index加一
}
// 客户1是客户2的子集
else if(slots2[i2][0]<=slots1[i1][0]
&&slots2[i2][1]>=slots1[i1][1]){
// 当客户1的时间区间长度大于等于duration
if(slots1[i1][1]-slots1[i1][0]>=duration){
// 返回合理区间
return getList(slots1[i1][0], duration);
}
i1++; // 客户1的index加一
}
// 客户1和客户2有部分交集（客户2在前）
else if(slots2[i2][1]>=slots1[i1][0]
&&slots2[i2][0]<slots1[i1][0]){
if(slots2[i2][1]-slots1[i1][0]>=duration){
return getList(slots1[i1][0], duration);
}
i2++;
}
// 客户1和客户2有部分交集（客户1在前）
else if(slots1[i1][1]>=slots2[i2][0]
&&slots1[i1][0]<slots2[i2][0]){
if(slots1[i1][1]-slots2[i2][0]>=duration){
return getList(slots2[i2][0], duration);
}
i1++;
}
}
return new ArrayList<>();
}
List<Integer> getList(int start, int duration){
List<Integer> res = new ArrayList<>();
res.add(start);
res.add(start+duration);
return res;
}本题解法执行时间为31ms。
Runtime: 31 ms, faster than 92.68% of Java online submissions for Meeting Scheduler.
Memory Usage: 48.2 MB, less than 100.00% of Java online submissions for Meeting Scheduler.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1229-meeting-scheduler-解题思路分析/