Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구현하는 회의 스케줄러: 두 사람의 공통 가용 시간대 찾기

문제 개요

두 사람의 가용 시간대 목록 slots1과 slots2, 그리고 회의 길이 d가 주어졌을 때, 두 사람 모두 참석할 수 있으면서 길이가 d 이상인 가장 빠른 시간대를 찾아야 합니다. 만약 조건을 만족하는 공통 시간대가 존재하지 않는다면 빈 배열을 반환합니다.

시간대는 [start, end] 형태의 두 원소를 가진 배열로 표현되며, start부터 end까지의 포함 범위를 나타냅니다. 또한 동일한 사람의 가용 시간대끼리는 서로 겹치지 않는다고 가정합니다. 즉, 같은 사람의 임의의 두 시간대 [s1, e1]과 [s2, e2]에 대해 항상 s1 > e2 또는 s2 > e1이 성립합니다.

예를 들어 입력이 s1 = [[10,50],[60,120],[140,210]], s2 = [[0,15],[60,70]], duration = 8이라면 출력은 [60,68]이 됩니다. 두 사람 모두 60분부터 70분 사이에 시간이 비어 있으므로, 60분부터 8분간 회의를 진행하면 되기 때문입니다.

알고리즘 접근 방식

이 문제는 정렬과 두 포인터(two-pointer) 기법을 조합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • 두 목록을 각각 시작 시간 기준으로 오름차순 정렬합니다.
  • 포인터 i와 j로 두 목록을 순회하면서 현재 시간대 쌍의 교집합 구간을 계산합니다.
  • 교집합의 시작점은 두 시작 시간 중 최댓값, 끝점은 두 종료 시간 중 최솟값입니다.
  • 교집합 길이가 duration 이상이면 즉시 답을 반환하고, 그렇지 않으면 종료 시간이 더 이른 쪽의 포인터를 앞으로 이동시킵니다.

구체적인 풀이 단계는 다음과 같습니다.

  1. i := 0, j := 0으로 초기화하고, 결과를 담을 배열 ans를 생성한 뒤 s1과 s2를 정렬합니다.
  2. i가 s1의 크기보다 작고 j가 s2의 크기보다 작은 동안 다음을 반복합니다.
    • end := s1[i][1]과 s2[j][1] 중 최솟값
    • start := s1[i][0]과 s2[j][0] 중 최댓값
    • 만약 end − start ≥ duration이면 ans에 start와 (start + duration)을 삽입하고 ans를 반환합니다.
    • 그렇지 않고 s1[i][1] < s2[j][1]이면 i를 1 증가시킵니다.
    • 그 외의 경우에는 j를 1 증가시킵니다.
  3. 반복문이 종료되면 ans를 반환합니다(조건을 만족하는 시간대가 없으면 빈 배열).

C++ 구현 예제

아래 코드를 통해 전체 로직을 더 자세히 살펴보겠습니다.

#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]

복잡도 분석 및 마무리

이 알고리즘은 두 목록을 정렬한 뒤 한 번의 순회만으로 답을 찾기 때문에 매우 효율적입니다. 시간 복잡도는 정렬에 O(n log n + m log m), 순회에 O(n + m)이며, 결과 배열 외에 추가 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다.

정렬 후 두 포인터를 활용해 교집합을 탐색하는 이 패턴은 회의 조율, 일정 관리 서비스 등 실무에서도 자주 응용되므로, 두 포인터 기법과 함께 확실히 익혀두는 것이 좋습니다.