k397 - 會議安排 (Meeting)
題目描述
題目給定兩個時間區間集合，分別代表兩個人的空閒時間。目標是找到一個長度至少為 x 的時間段，使得這段時間對兩個人來說都是空閒的，並輸出該時間段的起始時間和結束時間。如果找不到符合條件的時間段，則輸出 -1。
解題思路
這題可以使用貪心策略來解決。題目要求找到一個長度至少為 x 的共同空閒時間段。程式碼透過巢狀迴圈迭代兩個時間區間集合，計算它們的交集長度。如果交集長度大於或等於 x，則輸出交集的起始時間和結束時間，並立即結束程式。如果遍歷完所有可能的組合都找不到符合條件的時間段，則輸出 -1。
複雜度分析
- 時間複雜度: O(n*m)，其中 n 和 m 分別是兩個時間區間集合的大小。因為程式碼使用了巢狀迴圈來遍歷所有可能的組合。
- 空間複雜度: O(1)，程式碼只使用了常數級別的額外空間。
程式碼
#include <iostream>
using namespace std;
int n,m,a[105][2],b[105][2],x;
int main(){
cin >> n >> m;
for(int i=0;i<n;++i){
cin >> a[i][0] >> a[i][1];
}
for(int i=0;i<m;++i){
cin >> b[i][0] >> b[i][1];
}
cin >> x;
for(int i=0,j=0;i<n;++i){
for(int j=0;j<m;++j){
if(min(a[i][1],b[j][1])-max(a[i][0],b[j][0])>=x){
cout << max(a[i][0],b[j][0]) << " " << max(a[i][0],b[j][0])+x;
return 0;
}
}
}
cout << "-1";
}