LeetCode 1229. 安排會議日程（雙指針）

文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

你是一名行政助理，手裡有兩位客戶的空閑時間表：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            

複制

來源：力扣（LeetCode） 連結：https://leetcode-cn.com/problems/meeting-scheduler

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 先對兩個人的時間進行排序
• 然後雙指針周遊檢查即可

class Solution {
public:
    vector<int> minAvailableDuration(vector<vector<int>>& slots1, vector<vector<int>>& slots2, int duration) {
    	int m = slots1.size(), n = slots2.size(), i = 0, j = 0;
    	int l, r;
    	sort(slots1.begin(), slots1.end());
    	sort(slots2.begin(), slots2.end());
    	while(i < m && j < n)
    	{
    		if(slots1[i][1] <= slots2[j][0])//1的時間小了
    			i++;
    		else if(slots1[i][0] >= slots2[j][1])//2的時間小了
    			j++;
    		else//有交集
    		{
    			l = max(slots1[i][0], slots2[j][0]);
    			r = min(slots1[i][1], slots2[j][1]);
    			if(r-l >= duration)//交集滿足開會需要
    				return {l, l+duration};
    			if(slots1[i][1] >= slots2[j][1])
    				j++;//不滿足，1的時間還有多餘，2往後找
    			else
    				i++;//否則，1往後找
    		}
    	}
    	return {};
    }
};           

複制

596 ms 29.6 MB