Meeting Rooms LeetCode
Imagine multiple meetings are scheduled throughout the day, each represented by a time interval. The task is to determine if a person can attend all these meetings without overlaps. For instance, if we have meetings from 9:00 to 10:00 a.m. and another from 10:30 to 11:30 a.m., we could attend both as there’s a gap. This problem is crucial for time management and scheduling in various scenarios, from business meetings to event planning.
Problem statement
Given an array of meeting intervals, intervals where intervals[i] = [starti, endi], determine if a person can attend all meetings without any overlap.
Constraints:
intervals.lengthintervals[i].length
Now, let’s look at some examples to better understand this problem:
Knowledge test
Let’s take a short quiz to ensure we understand the problem correctly.
Can two meetings with times [[0, 10], [11, 12]] be scheduled without conflicts?
Yes
No
Algorithm
We can solve this problem by sorting the meetings based on their start times. Then, we iterate through the meetings and check if the current meeting starts before the previous meeting ends. If so, there's a conflict, and attending all meetings is impossible.
Now, let’s look at the following illustration to get a better understanding of the solution:
Coding example
Now, let’s look at the solution for this coding challenge.
def attend_all_meetings(intervals):# Sort meetings by start timeintervals.sort(key=lambda x: x[0])for i in range(len(intervals) - 1):# Check for overlapsif intervals[i][1] > intervals[i + 1][0]:return Falsereturn True#Driver codedef main():# Test casestest_cases = [[[0, 1], [2, 4], [1, 3], [5, 6]],[[7, 10], [2, 4], [1, 3], [5, 6]],[[0, 1], [1, 2], [2, 3], [3, 4]],[[1, 2], [2, 3], [1, 3], [3, 4]],[[0, 5], [1, 2], [3, 4], [6, 7]],[[7, 10], [2, 4]]]for i, meetings in enumerate(test_cases):print(f"Test Case {i+1}:",test_cases[i])if attend_all_meetings(meetings):print("You can attend all meetings without conflicts.\n")else:print("There are conflicts in the meeting schedule.\n")if __name__ == "__main__":main()
Time complexity
Sorting the meetings takes
Space complexity
The algorithm uses a constant extra space for variables, regardless of the number of meetings. Therefore, the space complexity is
