# Meeting Rooms

Clarify the problem:

- The problem requires determining whether a person can attend all the meetings based on the given schedule.
- We need to implement a function that takes a list of meeting intervals and returns a boolean indicating whether the person can attend all the meetings.

Analyze the problem:

- Input: A list of meeting intervals, where each interval is represented by a start and end time.
- Output: A boolean value indicating whether the person can attend all the meetings.
- Constraints:
- The input list is non-empty.
- Each meeting interval is represented by a pair of integers [start, end], where start < end.
- The start and end times are in the range of 0 to 10^9.
- The intervals may not be sorted, and they can overlap.

Design an algorithm:

- We can solve this problem by sorting the meeting intervals based on their start times.
- Then, we can iterate through the sorted intervals and check if there is any overlap between consecutive intervals.
- If we find any overlap, it means the person cannot attend all the meetings, and we return False.
- If we iterate through all the intervals without finding any overlap, it means the person can attend all the meetings, and we return True.

Explain your approach:

- We will implement a function called
`canAttendMeetings`

that takes a list of meeting intervals,`intervals`

, as input. - We will sort the intervals based on their start times using a custom comparison function.
- We will iterate through the sorted intervals and compare the end time of each interval with the start time of the next interval.
- If the end time is greater than or equal to the start time, it means there is an overlap, and we return False.
- If we iterate through all the intervals without finding any overlap, we return True.

- We will implement a function called
Write clean and readable code:

python`def canAttendMeetings(intervals): def compare(interval1, interval2): if interval1[0] < interval2[0]: return -1 elif interval1[0] > interval2[0]: return 1 else: return 0 intervals.sort(compare) for i in range(len(intervals) - 1): if intervals[i][1] > intervals[i + 1][0]: return False return True`

Test your code:

python`# Test case 1 # Intervals: [[0, 30], [5, 10], [15, 20]] # The intervals [5, 10] and [15, 20] overlap, so the person cannot attend all the meetings. assert canAttendMeetings([[0, 30], [5, 10], [15, 20]]) == False # Test case 2 # Intervals: [[7, 10], [2, 4]] # The intervals do not overlap, so the person can attend all the meetings. assert canAttendMeetings([[7, 10], [2, 4]]) == True # Test case 3 # Intervals: [[1, 5], [5, 10]] # The intervals overlap at the time 5, so the person cannot attend all the meetings. assert canAttendMeetings([[1, 5], [5, 10]]) == False`

Optimize if necessary:

- The current solution has a time complexity of O(n log n) due to the sorting operation, where n is the number of meeting intervals.
- This is the best time complexity we can achieve since we need to sort the intervals.
- There is no further optimization possible in terms of time complexity.

Handle error cases:

- The code assumes that the input list is non-empty and contains valid meeting intervals.
- It does not handle invalid input, such as empty lists or intervals with invalid start and end times.
- In such cases, the behavior of the code is undefined.

Discuss complexity analysis:

- The time complexity of the solution is O(n log n), where n is the number of meeting intervals.
- The space complexity is O(1) since we are not using any additional data structures.
- The best-case scenario occurs when there is only one meeting interval, and the function returns True in constant time.
- The worst-case scenario occurs when all the meeting intervals overlap, and the function iterates through all the intervals, taking O(n) time.
- The average-case time complexity is O(n log n), assuming random inputs.