题目描述

给定两个人的空闲时间表：slots1 和 slots2，以及会议的预计持续时间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
输出：[]

算法

(双指针) $O(n + m)$

题目大意是给定两个区间序列，找一个公共区间使得其长度等于duration

首先分别将两个区间序列排序，然后双指针i和j分别指向两个序列的首元素，开始遍历

对于当前的i和j：

1. 首先判断两个区间的交集长度是否满足要求，若满足，则直接输出答案
2. 若两个区间有交集，但交集长度不足，此时检查两个区间的左端点位置
   2.1 若i区间左端点更小，此时要检查i + 1区间是否与j有交集，若有，令i ++; 否则令j ++
   2.2 若j区间左端点更小，此时要检查j + 1区间是否与i有交集，若有，令j ++; 否则令i ++
3. 若两个区间直接没有交集，则要对应地移动i, j

时间复杂度

平均两个序列都要被遍历一次，所以时间复杂度是线性的

C++ 代码

class Solution {
public:
    int getDuration(vector<int>& a, vector<int>& b)
    {
        return min(a[1], b[1]) - max(a[0], b[0]);
    }
    int getStart(vector<int>& a, vector<int>& b)
    {
        return max(a[0], b[0]);
    }
    vector<int> minAvailableDuration(vector<vector<int>>& slots1, vector<vector<int>>& slots2, int duration) {
        vector<int> res;
        sort(slots1.begin(), slots1.end());
        sort(slots2.begin(), slots2.end());
        int n = slots1.size(), m = slots2.size();
        int i = 0, j = 0;
        while(i < n && j < m)
        {
            vector<int> a = slots1[i], b = slots2[j];
            if(getDuration(a, b) >= duration)
            {
                res.push_back(getStart(a, b));
                res.push_back(res[0] + duration);
                return res;
            }
            else if(getDuration(a, b) >= 0)
            {
                if(getStart(a, b) == a[0]) 
                {
                    if(i + 1 < n && getDuration(slots1[i + 1], b) >= 0) i ++;
                    else j ++;
                }
                else 
                {
                    if(j + 1 < m && getDuration(a, slots2[j + 1]) >= 0) j ++;
                    else i ++;
                }
            }
            else
            {
                if(a[1] < b[0]) i ++;
                else if(b[0] < a[1]) j ++;
            }
        }
        return res;
    }
};