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.

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.