Pramp - Time Planner

문제

[시작,종료]로 구성된 시작시간으로 정렬된 두명의 빈 가용시간 테이블이 주어진다. 주어진 dur 시간 만큼의 미팅을 하고자할때 현재 두 타임테이블에서 그것이 가능하다면 첫번째로 가능한 예약 시간을 리턴하라.

input:  slotsA = [[10, 50], [60, 120], [140, 210]]
        slotsB = [[0, 15], [60, 70]]
        dur = 8
output: [60, 68]

input:  slotsA = [[10, 50], [60, 120], [140, 210]]
        slotsB = [[0, 15], [60, 70]]
        dur = 12
output: [] # since there is no common slot whose duration is 12

해결 아이디어

          i
slotsA = [[10, 50], [60, 120], [140, 210]]
          j
slotsB = [[0, 15], [60, 70]]

• 두 Interval중 겹치는(Overlap) 시간계산은 아래와 같이 계산 할 수 있다. 공식처럼 필요할때 사용할 수 있을듯! 만약 답이 양수이면 겹치는 시간이 있다는 뜻.

  • A와 B에서 종료시간중 더 작은값 - 시작 시간 중 더 큰값
    가령 현재 A가 [10,50] 이고 B가 [0,15] 일때. 겹치는 시간을 계산하면 min(50,15) - max(10,0) => 5 가 된다.

• 따라서 이 overlap시간이 dur 시간보다 크다면 예약이 가능하다.

• 비교할 대상은 two pointer를 활용해서 i, j를 비교한다. 문제는 어떤조건에 i와 j를 증가시킬지이다.
  매 루프마다 종료값을 비교했을때 더 작은 요소의 인덱스를 증가시킨다. 아래예에서 같이 종료 값이 작은 요소B의 다음 요소가 A와 Overlap될 가능성이 있기에 B를 증가시켜서 확인한다. 그래야 모든 interval을 빠짐없이 확인 할수 있다.

       i
A      -------
    j      j+1
B   -----  ------   (j+1) 과 i 가 Overlap될 수 있음

해결 O(m+n)

vector<int> meetingPlanner( const vector<vector<int>>& slotsA, const vector<vector<int>>& slotsB, int dur) {
  int i = 0, j = 0;
  int min_end = 0, max_begin = 0;
  vector<int> ret;
  while (i < slotsA.size() && j < slotsB.size()) {
    // check with i,j
    min_end = min(slotsA[i][1], slotsB[j][1]);
    max_begin = max(slotsA[i][0], slotsB[j][0]);
    if (min_end - max_begin >= dur) {
      ret.push_back(max_begin);
      ret.push_back(max_begin + dur);
    }
    // moving two pointer
    if (slotsA[i][1] > slotsB[j][1])
      j++;
    else
      i++;
  }
  return ret;
}

int main() {
  return 0;
}