当前位置:   article > 正文

LeetCode 5089. 安排会议日程 Meeting Scheduler - Java_会议室时间编排 java

会议室时间编排 java

5089. 安排会议日程

你是一名行政助理,手里有两位客户的空闲时间表:slots1slots2,以及会议的预计持续时间 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]
  • 1
  • 2
  • 3
示例2
输入:slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]],
	duration = 12
输出:[]
  • 1
  • 2
  • 3
示例3
输入:slots1 = [[100,130],[50,80],[10,20]], slots2 = [[110,130],[60,80],[10,30]],
	duration = 20
输出:[60,80]
  • 1
  • 2
  • 3
提示
  • 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

题解

按照开始时间从小到大排序。然后查找即可。之前周赛做过 2 次类似的。唯一的不同就是要先排序。

我第一次提交就没排序。。示例要弄的这么坑。

判断条件:

  1. 如果某人的时间段 [start, end] 比会议时间还短,那肯定是不行的。
  2. 如果时间交叉部分比会议时间短,那也不行。交叉部分计算:一个人的结束时间减另一个人的开始时间。
  3. 如果交叉部分时间大于会议时间,那么符合要求,看谁开始的时间大,就在这个时间开会。

时间复杂度: 从前往后找,因此复杂度为 O ( n ) O(n) O(n)
空间复杂度: 用到几个常量,复杂度为 O ( 1 ) O(1) O(1)

Java代码

class Solution {
	public void doubleArraySort(int[][] srcArr,
								final int[] ordersArr) {
		// 按照ordersArr指定的列升序排序
		Arrays.sort(srcArr, new Comparator<Object>() {
			public int compare(	Object objOne,
								Object objTwo) {
				int[] arrOne = (int[]) objOne;
				int[] arrTwo = (int[]) objTwo;
				for (int k : ordersArr) {
					if (arrOne[k] > arrTwo[k]) {
						return 1;
					} else if (arrOne[k] < arrTwo[k]) {
						return -1;
					} else {
						continue;
					}
				}
				return 0;
			}
		});
	}

	public List<Integer> minAvailableDuration(	int[][] slots1,
												int[][] slots2,
												int duration) {
		doubleArraySort(slots1, new int[] { 0 });
		doubleArraySort(slots2, new int[] { 0 });
		int s1 = 0, s2 = 0;
		List<Integer> ret = new ArrayList<Integer>();
		while (s1 < slots1.length && s2 < slots2.length) {
			int st1 = slots1[s1][0];
			int en1 = slots1[s1][1];
			int st2 = slots2[s2][0];
			int en2 = slots2[s2][1];
			if (en1 - st1 < duration) {
				++s1;
				continue;
			}
			if (en2 - st2 < duration) {
				++s2;
				continue;
			}
			if (en1 - st2 < duration) {
				++s1;
				continue;
			}
			if (en2 - st1 < duration) {
				++s2;
				continue;
			}
			int begin = Math.max(st1, st2);
			ret.add(begin);
			ret.add(begin + duration);
			break;
		}
		return ret;
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/182149?site
推荐阅读
相关标签
  

闽ICP备14008679号