문제

Given an array of intervals representing ‘N’ appointments, find out if a person can attend all the appointments.

input & output

Example 1

Appointments: [[1,4], [2,5], [7,9]]
Output: false

Explanation: Since [1,4] and [2,5] overlap, a person cannot attend both of these appointments.

Example 2

Appointments: [[6,7], [2,4], [8,12]]
Output: true

Explanation: None of the appointments overlap, therefore a person can attend all of them.

Example 3

Appointments: [[4,5], [2,3], [3,6]]
Output: false

Explanation: Since [4,5] and [3,6] overlap, a person cannot attend both of these appointments.

---

Approach #1

배열 첫번째 인덱스 기준으로 정렬.

curInterval = stack[stack.length-1];
for(appointment of appointments)

[1,4] [2,5]
if 4 > 2 이면 들어갈수 있음. false. 
else 면 stack.push()

다 보고 나오면 return true;

Solution #1

function attendAppointments(appointments){
  appointments.sort((a,b) => a[0]-b[0]);
  const stack = [appointments[0]];

  for(let i=1; i<appointments.length; i++){
    let curArr = stack[stack.length-1];
    let appointment = appointments[i];
    if(curArr[1] > appointment[0]) return false;
    else stack.push(appointment);
  }
  return true;
}

N:appointments.length
M:stack.length

Time Complexity

O(NlogN)+O(N)

appointments 배열 정렬하는데 O(NlogN), for문 돌때 O(N).

Space Complexity

O(N)

스택이 최대로 쌓였을때가 appointments.length(N)만큼이므로 공간복잡도는 O(N).

---

Approach #2

배열 첫번째 인덱스 기준으로 정렬.


 pre   cur
[1,4] [2,5]
if 4 > 2 이면 약속이 겹침. false. 

다 보고 나오면 return true;

Solution #2

function attendAppointments2(appointments){
  appointments.sort((a,b) => a[0]-b[0]);
  for(let i=1; i<appointments.length; i++) {
    const curAps = appointments[i];
    const preAps = appointments[i-1];

    if(preAps[1] > curAps[0]) return false;
  }
  return true;
}

N:appointments.length

Time Complexity

O(NlogN + N)

배열 정렬할때 O(NlogN), for문 돌면서 확인할때 O(N).

Space Complexity

O(1)

함수내에서 추가적인 공간 할당하지 않으므로 O(1).

---