가용 시간 슬롯에 두 사람의 슬롯 1과 슬롯 2가 있고 회의 기간 d가 있다고 가정하면 두 사람 모두에게 작동하고 지속 시간이 d인 가장 빠른 시간 슬롯을 찾아야 합니다. 요구 사항을 충족하는 공통 시간 슬롯이 없으면 빈 배열을 표시합니다. 여기에서 시간 슬롯의 형식은 시작부터 끝까지 포함하는 시간 범위를 나타내는 두 요소 [start, end]의 배열입니다. 동일한 사람의 두 가용성 슬롯이 서로 교차하지 않는다고 가정할 수 있습니다. 즉, 동일한 사람의 두 시간 슬롯 [s1, e1] 및 [s2, e2]에 대해 s1> e2 또는 s2> e입니다. 따라서 입력이 s1 =[[10,50], [60,120], [140,210]] 및 s2 =[[0,15], [60,70]] 및 duration =8과 같으면 출력은 [ 60,68].
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- i :=0 및 j :=0, 하나의 배열을 ans로 만들고 s1과 s2를 정렬합니다.
- i
- end :=s1[i, 1] 및 s2[j, 1]의 최소값
- 시작:=s1[i, 0] 및 s2[j, 0]의 최소값
- 종료일 경우 시작>=기간인 경우
- as 배열에 start 및 (start + duration)을 삽입하고 as를 반환합니다.
- 그렇지 않으면 s1[i, 1]
- 그렇지 않으면 j를 1만큼 증가
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#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, ]