Meeting Rooms

Problem Statement

Given an array of meeting time interval objects consisting of start and end times [[start_1,end_1],[start_2,end_2],...] (start_i < end_i), determine if a person could add all meetings to their schedule without any conflicts.

Example 1:

# Definition for an interval.
class Interval:
    def __init__(self, start=0, end=0):
        self.start = start
        self.end = end


intervals = [Interval(0,30), Interval(5,10), Interval(15,20)]


#Output: false

Explanation:

  • (0,30) and (5,10) will conflict
  • (0,30) and (15,20) will conflict

Example 2:

# Definition for an interval.
class Interval:
    def __init__(self, start=0, end=0):
        self.start = start
        self.end = end


intervals = [Interval(5,8), Interval(9,15)]


#Output: true

Note:

  • (0,8),(8,10) is not considered a conflict at 8

Constraints:

  • 0 <= intervals.length <= 500
  • 0 <= intervals[i].start < intervals[i].end <= 1,000,000

You should aim for a solution with O(n log n) time complexity due to sorting. Space complexity can be O(1) if sorting is done in-place, or O(n) otherwise.

Hint 1

Think about what needs to be true for a person to attend all meetings.

Hint 2

If the meetings are sorted by start time, is there a simple way to check for overlaps?

Hint 3

Sort the intervals based on start times. Then, iterate through the sorted intervals and check for overlaps between adjacent intervals.

Solution

Brute Force

"""
Definition of Interval:
class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
"""


def can_attend_meetings(intervals: list[Interval]) -> bool:
    n = len(intervals)
    for i in range(n):
        a = intervals[i]
        for j in range(i + 1, n):
            b = intervals[j]
            if min(a.end, b.end) > max(a.start, b.start):
                return False
    return True

Time complexity: O(n^2) Space complexity: O(1)

Sorting

"""
Definition of Interval:
class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
"""


def can_attend_meetings(intervals: list[Interval]) -> bool:
    intervals.sort(key=lambda i: i.start)


    for i in range(1, len(intervals)):
        i1 = intervals[i - 1]
        i2 = intervals[i]


        if i1.end > i2.start:
            return False
    return True

Time complexity: O(n log n) Space complexity: O(1) or O(n) depending on the sorting algorithm.