LeetCode #252: Meeting Rooms

https://leetcode.com/problems/meeting-rooms/description/

In this problem, we are given a list of intervals, each representing a meeting start and end time, and we need to determine if it is possible for a person to attend all the meetings without any overlapping schedules.

One simple way to solve this problem is to sort the intervals based on their start times, and then check if any two adjacent intervals overlap. If there is an overlap, then it is not possible to attend all the meetings.

Here are the steps to solve the problem:

1. Sort the intervals based on their start times.
2. Iterate through the intervals from the first to the second to the last interval.
3. For each pair of adjacent intervals, check if the end time of the first interval is greater than or equal to the start time of the second interval.
4. If there is any overlap, return False.
5. If we reach the end of the loop without finding any overlap, return True.

Let’s take a look at the solution:

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

Time and Space Complexity

The time complexity of this solution is O(nlogn) because of the sorting step, where n is the number of intervals. The space complexity is O(1) because we only use constant extra space.