資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++會議排程器
假設我們有兩個人的可用時間段列表slots1和slots2，以及會議時長d，我們需要找到對他們兩個都適用且時長為d的最早時間段。如果沒有滿足要求的公共時間段，則顯示空陣列。這裡時間段的格式是由兩個元素[開始時間, 結束時間]組成的陣列，表示從開始時間到結束時間的包含範圍。我們可以假設同一個人的任何兩個可用時間段不會相互重疊。也就是說，對於同一個人的任何兩個時間段[s1, e1]和[s2, e2]，要麼s1 > e2，要麼s2 > e1。例如，如果輸入為s1 = [[10,50], [60,120], [140,210]]，s2 = [[0,15], [60,70]]，時長 = 8，則輸出為[60,68]。
為了解決這個問題，我們將遵循以下步驟：
- i := 0，j := 0，建立一個數組ans，對s1和s2進行排序。
- 當i < s1的大小 且 j < s2的大小時
- end := s1[i, 1] 和 s2[j, 1]中的最小值
- start := s1[i, 0] 和 s2[j, 0]中的最小值
- 如果 end – start >= duration，則
- 將start和(start + duration)插入ans陣列，並返回ans。
- 否則，如果s1[i, 1] < s2[j, 1]，則將i加1
- 否則將j加1
- 返回ans
讓我們看看下面的實現來更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
using namespace std;
bool cmp(vector <int> a, vector <int> b){
return a[0]<b[0];
}
class Solution {
public:
vector<int> minAvailableDuration(vector<vector<int>>& slots1, vector<vector<int>>& slots2, int duration) {
int i =0;
int j = 0;
vector <int> ans;
sort(slots1.begin(),slots1.end(),cmp);
sort(slots2.begin(),slots2.end(),cmp);
while(i<slots1.size() && j<slots2.size()){
int end = min(slots1[i][1],slots2[j][1]);
int start = max(slots1[i][0],slots2[j][0]);
if(end-start>=duration){
ans.push_back(start);
ans.push_back(start+duration);
return ans;
} else if(slots1[i][1]<slots2[j][1]) {
i++;
} else {
j++;}
}
return ans;
}
};
main(){
vector<vector<int>> v = {{10,50},{60,120},{140,210}};
vector<vector<int>> v1 = {{0,15},{60,70}};
Solution ob;
print_vector(ob.minAvailableDuration(v, v1, 8));
}輸入
[[10,50],[60,120],[140,210]] [[0,15],[60,70]] 8
輸出
[60, 68, ]
更新於：2020年4月30日
901 次檢視
廣告