Katkat
Back

Determine Whether One Person Can Attend Every Meeting

AmazonSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to handle interval sorting and linear-time overlap detection to ensure no two meetings conflict.

Determine Whether One Person Can Attend Every Meeting

Given a list of meeting time intervals, where each interval is represented as a pair of integers [start, end], write a function to determine if a person can attend all meetings. Assume that a meeting occupies the time from start to end (exclusive of the end time), meaning two meetings [1, 2] and [2, 3] do not overlap.

Function Signature

def can_attend_meetings(intervals: list[list[int]]) -> bool:

Constraints

  • 0 <= intervals.length <= 10,000
  • 0 <= start < end <= 1,000,000

Examples

Example 1:

  • Input: intervals = [[0, 30], [5, 10], [15, 20]]
  • Output: False
  • Explanation: The meeting [0, 30] overlaps with [5, 10] and [15, 20].

Example 2:

  • Input: intervals = [[7, 10], [2, 4]]
  • Output: True
  • Explanation: There are no overlapping intervals.

Edge Cases

  • An empty list of meetings should return True.
  • Meetings that start exactly when the previous meeting ends (e.g., [1, 2] and [2, 3]) are valid and should not be considered overlaps.

Hints

Hint 1

Consider that sorting the intervals by their start times makes it significantly easier to identify potential conflicts.

Hint 2

Once sorted, you only need to compare the end time of one meeting with the start time of the next meeting in the sequence.

Hint 3

If any meeting starts before the previous one ends, you can immediately conclude that attendance is impossible.

Follow-up questions

  • What is the time and space complexity of your solution, and can you optimize the space complexity to O(1) if you are allowed to modify the input list?
  • If the input was not a list of intervals but a stream of meetings, how would you approach the problem?
  • How would you modify this algorithm if you were asked to return the minimum number of meeting rooms required instead of a boolean value?