Meeting Rooms - Leetcode Solution

The Meeting Rooms problem on LeetCode requires us to determine if a set of meeting times overlaps.

The problem can be described in this way:

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

Example:

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

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

We can solve this problem using a greedy approach. We can sort the intervals based on their start times, and then iterate over the sorted array, checking if the current interval overlaps with the previous interval. If there is an overlap, we return False, since it's not possible to attend both meetings. If there is no overlap, we continue iterating.

Here's the Python implementation:

def canAttendMeetings(intervals):
    intervals.sort(key=lambda x: x[0])
    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i-1][1]:
            # There is an overlap
            return False
    return True

We start by sorting the intervals based on their start times:

intervals.sort(key=lambda x: x[0])

Then, we iterate over the sorted intervals, checking for overlaps:

for i in range(1, len(intervals)):
    if intervals[i][0] < intervals[i-1][1]:
        # There is an overlap
        return False

If there is an overlap, we return False. If there is no overlap, we continue iterating. If we reach the end of the array without finding an overlap, we return True:

return True

The time complexity of this algorithm is O(n log n) because of the sorting, and the space complexity is O(1) because we are not using any additional data structures.

1