【LeetCode - 1229】安排会议日程_力扣1229安排会议

1、题目描述

2、解题思路

  题目保证了同一个人的空闲时间不会出现交叠的情况，于是先把两个人的空闲时间表按照开始时间从小到大排序。

  排序后的时间表假设如下：

  slots1 = [[10,50],[60,120],[140,210]]

  slots2 = [[0,15],[60,70]]

  定义一个变量 idx1 用于遍历 slots1，idx2 用于遍历 slots2。

  假设 duration 为 8：

  1、对于初始的 [10, 50] 和 [0, 15] ，看出开始最早的是客户 2，结束最晚的是客户 1，交集就是 [10, 15] 发现小于 duration，因为结束最晚的是客户 1，于是客户 1 的索引不动，因为可能交集还是在客户 1 当前的 [10, 50] 区间内，让 idx2++；

  2、此时两个时间表为 [10, 50] 和 [60, 70]，没有交集，应该继续找下一个时间表，因为此时结束时间最晚的是客户 2，可能的目标交集会在 [60, 70] ，于是让 idx1++；

  3、此时两个时间表为 [60, 120] 和 [60, 70]，开始最晚的时间是 60，结束最早的时间是 70，满足 duration，于是返回 [最晚开始时间, 最晚开始时间+duration]

3、解题代码

class Solution {
    public List<Integer> minAvailableDuration(int[][] slots1, int[][] slots2, int duration) {
        // 给两个客户按照开始时间排序他们的时间表
        Arrays.sort(slots1, (a, b) -> (a[0] - b[0]));
        Arrays.sort(slots2, (a, b) -> (a[0] - b[0]));
        int idx1 = 0, idx2 = 0;
        // 遍历两个客户的时间表
        while (idx1 < slots1.length && idx2 < slots2.length) {
            // 当前遍历到的 slots 的末尾值
            int ed1 = slots1[idx1][1];
            int ed2 = slots2[idx2][1];
            // 当前 slots 的最晚开始时间
            int st = Math.max(slots1[idx1][0], slots2[idx2][0]);    // 最晚开始时间
            if (ed1 > ed2) {    // 1 的时间比较宽
                if (ed2 - st >= duration) {
                    return Arrays.asList(st, st + duration);
                }
                idx2++;
            } else { // 2 的时间比较宽
                if (ed1 - st >= duration) {
                    return Arrays.asList(st, st + duration);
                }
                idx1++;
            }
        }
        return new ArrayList<>();
    }
}
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