Teaching Kids Programming – Algorithms to Check If Any Intervals Overlapping (Meeting Rooms)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

Example 1:
Input: intervals = [[0,30],[5,10],[15,20]]
Output: false

Example 2:
Input: intervals = [[7,10],[2,4]]
Output: true

Constraints:
0 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= starti < endi <= 10^6

Bruteforce Algorithm to Check If Any Intervals Overlapping

If any two meetings (intervals) overlap, then we can’t attend all the meetings. Thus we can bruteforce all pairs of meetings in O(N^2) to see if they overlap. To find out if two meetings overlap, we check their ends:

overlapping-interval

The overall time complexity is O(N^2).

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        n = len(intervals)
        
        def overlap(a, b):
            return min(a[1], b[1]) > max(a[0], b[0])
        
        for i in range(n):
            for j in range(i):
                if overlap(intervals[i], intervals[j]):
                    return False
        return True

class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        n = len(intervals)
        
        def overlap(a, b):
            return min(a[1], b[1]) > max(a[0], b[0])
        
        for i in range(n):
            for j in range(i):
                if overlap(intervals[i], intervals[j]):
                    return False
        return True

Sorting Algorithm to Check If Any Intervals Overlapping

If we sort the intervals by their start, we can check if the current meeting is overlapping with the next one.

1
2
3
4
5
6
7
8

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

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

Sorting takes O(NLogN) time complexity, we can rewrite above using one-liner via all or any method:

1
2

return all(intervals[i][1] <= intervals[i + 1][0] for i in range(n - 1))
return not any(intervals[i][1] > intervals[i + 1][0] for i in range(n - 1))

return all(intervals[i][1] <= intervals[i + 1][0] for i in range(n - 1))
return not any(intervals[i][1] > intervals[i + 1][0] for i in range(n - 1))

–EOF (The Ultimate Computing & Technology Blog) —