[ leetcode 문제풀이 ] Meeting Rooms

https://leetcode.com/problems/meeting-rooms/

Account Login - LeetCode

(Meeting Rooms 문제는 LeetCode Premium 문제로 위 링크 혹은 LintCode를 통해 풀어보실 수 있습니다.)

 

 

 

< Meeting Rooms 문제 설명 >

 

Meeting Rooms 문제는 다음과 같다.

Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.

 

intervals[i]가 회의의 시작과 끝 시간([starti, endi])를 나타내는 intervals 배열이 주어질 때, 한 사람이 모든 회의에 참여할 수 있는지를 판단하여라.

 

다음 두 가지 출력 예시가 주어졌다.

 

 

주어진 제한 조건은 다음과 같다:

0  ≤  intervals.length  ≤  10^4

intervals[i].length == 2

0  ≤  starti  <  endi  ≤ 10^6

 

 

 

---

< Meeting Rooms 문제 접근 >

 

이 문제의 input intervals의 interval에 대해 하나라도 서로 겹친다면 false가 된다. intervals가 non-overlapping 이어야 한다는 뜻이고, 이는 sorting을 통해 알 수 있다. 회의의 시작시간을 기준으로 intervals를 sorting한 후 각 회의의 종료시간이 다음 회의의 시작시간보다 늦는다면 false를 리턴하도록 하였다. 작성한 코드는 다음과 같다. (Cpp 사용)

 

#include <algorithm>

bool canAttendMeetings(vector<vector<int>>& intervals){
    int n = intervals.size();
    if(!n) return true; // interval이 비어있는 경우 처리
    
    sort(intervals.begin(), intervals.end());
    
    for(int i=1;i<n;i++)
        if(intervals[i-1][1] > intervals[i][0])
            return false;
    
    return true;
} // runtime : 61 ms, memory usage : 5.52 MB (by LintCode)

 

이 코드에서 for문은 interval을 단순히 살펴보는 것이므로 O(n)이고, 시간복잡도를 좌우하는 과정은 sorting이므로 알고리즘의 시간복잡도는 sorting의 시간복잡도인 O(n log n)이 된다.