920 · Meeting Rooms

문제 링크 :
https://www.lintcode.com/problem/920/

주어진 intervals에서 미팅의 시작시간과 끝나는 시간 start와 end가 주어진다.([[s1,e1],[s2,e2],...])

만약 모든 미팅에 참여할 수 있으면 True, 그렇지 않으면 False를 반환한다.

만약
intervals = [(5,8),(9,15)]
처럼
어떤 미팅의 시작 시간과 다음 미팅의 시작시간이 겹치지 않으면 모든 미팅에 참여할 수 있으므로 True를 반환할 수 있다.
(5,8)미팅 참여하고 그 다음 (9,15)미팅에 참여하면 됨.

따라서 각 미팅들의 끝나는 시간과 다음 미팅의 시작시간을 비교하여 풀수 있다

def can_attend_meetings(self, intervals: List[Interval]) -> bool:
        intervals.sort(key= lambda i: i.start)
        #오름차순 안해주면 [(15,10),(0,9)]같은 테케에 걸릴수도
        for i in range(1,len(intervals)):
            if intervals[i-1].end>intervals[i].start:
                return False
        return True

시간 복잡도는 O(nlogn)

22.12.02 복습