题目描述

你是一名行政助理，手里有两位客户的空闲时间表：slots1 和 slots2，以及会议的预计持续时间 duration，请你为他们安排合适的会议时间。

「会议时间」是两位客户都有空参加，并且持续时间能够满足预计时间 duration 的 最早的时间间隔。

如果没有满足要求的会议时间，就请返回一个 空数组。

「空闲时间」的格式是 [start, end]，由开始时间 start 和结束时间 end 组成，表示从 start 开始，到 end 结束。

题目保证数据有效：同一个人的空闲时间不会出现交叠的情况，也就是说，对于同一个人的两个空闲时间 [start1, end1] 和 [start2, end2]，要么 start1 > end2，要么 start2 > end1。

样例

输入：
slots1 = [[10,50],[60,120],[140,210]],
slots2 = [[0,15],[60,70]],
duration = 8

输出：[60,68]

输入：
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

算法

(贪心，双指针) $O(n \log n)$

1. 首先将两个人的时间表从小到大排序。
2. 我们用 i 表示第一个人当前的时间段，j 表示第二个人。
3. 对于一个重合的时间段，[s1, e1] 和 [s2, e2]，如果 s2 <= s1 <= e2，则说明 i 开始的较晚，我们判断 min(e1, e2) - s1 是否满足 duration，若满足，则可以返回答案。若不满足，则根据 e1 和 e2 的大小关系推进 i 或 j。
4. 如果 j 开始的较晚同理。

时间复杂度

• 排序后，每个时间段最多扫描一次，故时间复杂度为 $O(n \log n)$。

空间复杂度

• 只需要常数的额外空间。

C++ 代码

class Solution {
public:
    vector<int> minAvailableDuration(vector<vector<int>>& slots1, vector<vector<int>>& slots2, int duration) {
        int n = slots1.size(), m = slots2.size();
        auto cmp = [&](const vector<int>& x, const vector<int> &y) {
            return x[0] < y[0];
        };

        sort(slots1.begin(), slots1.end(), cmp);
        sort(slots2.begin(), slots2.end(), cmp);

        vector<int> ans;
        int i = 0, j = 0;

        while (i < n && j < m) {
            while (i < n && slots1[i][1] < slots2[j][0]) i++;
            if (i == n) break;

            while (j < m && slots2[j][1] < slots1[i][0]) j++;
            if (j == m) break;

            int s1 = slots1[i][0], e1 = slots1[i][1], s2 = slots2[j][0], e2 = slots2[j][1];

            if (s2 <= s1 && s1 <= e2) {
                if (min(e1, e2) - s1 >= duration) {
                    ans.push_back(s1);
                    ans.push_back(s1 + duration);
                    break;
                } else {
                    if (e1 < e2) i++;
                    else j++;
                }
            } else if (s1 <= s2 && s2 <= e1) {
                if (min(e1, e2) - s2 >= duration) {
                    ans.push_back(s2);
                    ans.push_back(s2 + duration);
                    break;
                } else {
                    if (e1 < e2) i++;
                    else j++;
                }
            }
        }

        return ans;
    }
};