Katkat
Back

Measure Meeting Coverage and Required Rooms

FlexportSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to manipulate interval data, specifically calculating the total coverage area and finding the maximum concurrency using a sweep-line algorithm.

Meeting Optimization

You are given a list of meeting intervals represented as tuples (start, end), where start is inclusive and end is exclusive. You must perform two tasks:

  1. Calculate the total unique time duration covered by at least one meeting.
  2. Determine the minimum number of meeting rooms required to accommodate all meetings simultaneously at peak demand.

Function Signature

def analyze_meetings(intervals: list[tuple[int, int]]) -> tuple[int, int]:
    # Returns (total_covered_duration, min_rooms_required)

Constraints

  • 0 = end by ignoring them.

Examples

Example 1: Input: [(1, 4), (2, 5), (7, 9)]

  • Total duration: (1 to 5) = 4 plus (7 to 9) = 2, total = 6.
  • Min rooms: At time 2, we have two meetings active. Output: (6, 2)

Example 2: Input: [(1, 3), (3, 5)]

  • Total duration: (1 to 5) = 4.
  • Min rooms: Since one ends at 3 and another starts at 3, they do not overlap. Output: (4, 1)

Edge Cases

  • Empty list returns (0, 0).
  • Meetings that start and end at the same time are ignored.
  • Touching intervals (e.g., (1, 3) and (3, 5)) should not count as overlapping for room allocation.

Hints

Hint 1

To calculate the total duration, merge overlapping intervals first by sorting them by start time.

Hint 2

For the minimum number of rooms, use the sweep-line approach by treating starts as +1 and ends as -1 events, sorting them by time.

Hint 3

If two events occur at the same time, process the 'end' event before the 'start' event to correctly handle non-overlapping touching intervals.

Follow-up questions

  • How would your approach change if you were required to track the number of rooms needed at any specific point in time t?
  • If the input intervals were not in memory but arrived as a stream, how would you maintain the total duration?
  • What is the time and space complexity of your solution, and can you improve the space complexity if the range of times is very small?