Optimal Meeting Scheduler

Data Structures Algorithm Scheduling

Problem Description

You are given the availability intervals of several individuals for a single day. Each individual's availability is represented as a list of intervals, where each interval is a pair of integers [start, end] corresponding to the start time and end time in minutes since midnight (0 ≤ start < end ≤ 1440).

Your task is to write a function that, given:

  • A list of lists of intervals (one list per person), and
  • A desired meeting duration (in minutes),

finds all possible time slots during the day where a meeting of the given duration can be scheduled such that all individuals are available. Return the results as a list of intervals where each interval is at least as long as the desired meeting duration.

Requirements

  • The meeting must fit entirely inside a single interval where everyone is available.
  • If there is an overlapping interval of availability across all individuals that is longer than the required duration, it should be included.
  • The returned intervals should be sorted by start time.

Input Format

The input consists of:

  1. A list of lists of intervals, where each inner list is sorted by start time and represents the available time slots for one person.
  2. An integer representing the meeting duration in minutes.

Example

For example, suppose you have the following availabilities (times in minutes):

  • Person 1: [[60, 120], [150, 210], [300, 360]]
  • Person 2: [[0, 90], [100, 200], [250, 400]]

And the meeting duration is 30 minutes. The overlapping available slots between both persons are:

  • Overlap between [60, 120] and [0, 90] is [60, 90] (30 minutes, valid)
  • Overlap between [150, 210] and [100, 200] is [150, 200] (50 minutes, valid)
  • Overlap between [300, 360] and [250, 400] is [300, 360] (60 minutes, valid)

Your function should return: [[60, 90], [150, 200], [300, 360]].

Bonus

Consider optimizing your solution for the case where the input size is very large (for example, thousands of individuals with multiple intervals each). Think about the data structures and algorithms that can help you maintain efficiency.

Happy coding!