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