Meeting Rooms

Patrick Leaton
Published: March 29, 2021, 8:26 p.m.
Problem Description

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.length == 2
  • 0 <= starti < endi <= 10^6

 

The description was taken from https://leetcode.com/problems/meeting-rooms/.

Problem Solution

#O(N(Log(N)) Time, O(1) Space
class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        intervals.sort()
        for i in range(0, len(intervals)-1):
            if intervals[i][1] > intervals[i+1][0]:
                return False
        return True

Problem Explanation

The brute force method of solving this question would be to compare each interval with each other interval and see if the timespan overlaps.  That would require quadratic time.

If a meeting were to overlap with the next one, that would mean that the current meetings' end time is greater than the next meetings' start time.

With that in mind, we can solve this problem by sorting the intervals and see if the ending time of the current interval overlaps with the starting time of the next interval.

Let's start by sorting the intervals.

        intervals.sort()

 

After, we will traverse the sorted intervals and see if the ending time of the current iteration's interval overlaps with the starting time of the next interval.

If it does, we will return false.

        for i in range(0, len(intervals)-1):
            if intervals[i][1] > intervals[i+1][0]:
                return False

 

If we have traversed all of the intervals and haven't found any overlapping times, we will return true.

        return True