[Leetcode]252. Meeting Rooms

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.
Example 1:
Input: [[0,30],[5,10],[15,20]] Output: false

Probably one of the most simple solutions is to compare each of them to others with O(n^2) time complexity – for two slots [si,ei] and [sj,ej], check whether sj<si<ej or si<sj<ei.

Thinking further, we notice that we don’t have to compare one to all others – when we sort them first, we only need to compare the adjacent ones – and this achieves O(nlogn) which mainly lies on sorting.

Sort on start.

class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        intervals.sort(key=lambda x:x[0])
        for i in range(1,len(intervals)):
            if intervals[i][0]<intervals[i-1][1]:
                return False
        return True

Sort on end.

class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        intervals.sort(key=lambda x:x[1])
        for i in range(1,len(intervals)):
            if intervals[i][0]<intervals[i-1][1]:
                return False
        return True