Frontend School

Find Available Meeting Slots

DSA
medium

Find Available Meeting Slots

Medium
Intervals
Arrays
Sorting

Overview

At Apple, efficient scheduling is crucial for collaboration across teams and time zones. Imagine you're building a feature for a new internal scheduling tool that helps employees find optimal meeting times. This problem asks you to identify all available time slots for a meeting of a specified duration, given an employee's existing busy schedule and their defined working hours. The goal is to maximize productivity by quickly pinpointing when an employee can realistically attend a new meeting.

What you need to do / Task

You are tasked with implementing a function that calculates an employee's free time slots within their working hours, considering their existing commitments.

  1. Consolidate Busy Intervals: First, process the given list of busy intervals to merge any overlapping or contiguous busy periods into a single, comprehensive list of occupied times.
  2. Identify Gaps: Next, determine all periods within the employee's workingHours that are not covered by the consolidated busy intervals. These are the potential free slots.
  3. Filter by Duration: Finally, from these potential free slots, select only those that are long enough to accommodate a meeting of meetingDuration minutes.
  4. Return Results: The final list of available slots should be presented in the same HHMM format as the input.

Input & output

The function signature is findAvailableSlots(busyIntervals: number[][], meetingDuration: number, workingHours: number[]): number[][].

  • busyIntervals: An array of [start, end] pairs, where start and end are integers representing times in HHMM format (e.g., 900 for 9:00 AM, 1730 for 5:30 PM). Each interval [start, end] signifies that the employee is busy from start up to, but not including, end. These intervals are not necessarily sorted and may overlap.
  • meetingDuration: An integer representing the required duration of the meeting in minutes.
  • workingHours: A [start, end] pair, also in HHMM format, defining the employee's total available working period for the day. Similar to busyIntervals, [start, end] means from start up to, but not including, end.

The function should return an array of [start, end] pairs, representing the available time slots in HHMM format, sorted by their start times. Each returned slot must be at least meetingDuration minutes long.

Clarifications

  • Time Format: All times are in HHMM format. For example, 100 means 1:00 AM, 930 means 9:30 AM, 1700 means 5:00 PM. Assume valid 24-hour format where HH is 00-23 and MM is 00-59.
  • Interval Definition: An interval [start, end] means the period starting exactly at start and ending just before end. For example, [900, 1000] represents the hour from 9:00 AM to 9:59 AM.
  • Empty busyIntervals: If busyIntervals is empty, the entire workingHours period (if long enough) is considered available.
  • No Available Slots: If no slots meet the criteria, return an empty array [].

Examples

1

Example 1

Input:

busyIntervals = [[900, 1030], [1100, 1200], [1000, 1030]], meetingDuration = 30, workingHours = [800, 1800]

Output:

[[800, 900], [1030, 1100], [1200, 1800]]

Note:

  1. Sorted busy intervals: [[900, 1030], [1000, 1030], [1100, 1200]]
  2. Merged busy intervals: [[900, 1030], [1100, 1200]]
  3. Working hours: [800, 1800] (8:00 AM to 6:00 PM)
  4. Gaps within working hours:
    • [800, 900] (duration: 60 minutes)
    • [1030, 1100] (duration: 30 minutes)
    • [1200, 1800] (duration: 360 minutes)
  5. All gaps are at least 30 minutes long.
2

Example 2

Input:

busyIntervals = [[900, 1000], [1000, 1100]], meetingDuration = 60, workingHours = [800, 1200]

Output:

[[800, 900], [1100, 1200]]

Note:

  1. Sorted busy intervals: [[900, 1000], [1000, 1100]]
  2. Merged busy intervals: [[900, 1100]] (contiguous intervals merge)
  3. Working hours: [800, 1200]
  4. Gaps within working hours:
    • [800, 900] (duration: 60 minutes)
    • [1100, 1200] (duration: 60 minutes)
  5. Both gaps are 60 minutes long, meeting the meetingDuration.
3

Example 3

Input:

busyIntervals = [[900, 1700]], meetingDuration = 120, workingHours = [800, 1800]

Output:

[]

Note:

  1. Merged busy intervals (already merged): [[900, 1700]]
  2. Working hours: [800, 1800]
  3. Gaps within working hours:
    • [800, 900] (duration: 60 minutes)
    • [1700, 1800] (duration: 60 minutes)
  4. Neither of these gaps is long enough to accommodate a meetingDuration of 120 minutes. Therefore, no available slots.

Constraints

Constraints & assumptions

  • 0 <= busyIntervals.length <= 100
  • busyIntervals[i].length === 2
  • 0 <= busyIntervals[i][0] < busyIntervals[i][1] <= 2400
  • 1 <= meetingDuration <= 1440 (a full day)
  • workingHours.length === 2
  • 0 <= workingHours[0] < workingHours[1] <= 2400
  • All times are valid HHMM format.
  • workingHours[0] will always be less than workingHours[1].
  • All busyIntervals are within a single day.
  • The output intervals must be sorted by start time.

What interviewers evaluate

  • Algorithmic Efficiency: The ability to design an efficient algorithm, especially regarding sorting and merging intervals (e.g., time and space complexity).
  • Correctness and Edge Cases: Handling various scenarios correctly, including empty inputs, overlapping intervals, contiguous intervals, and no available slots.
  • Code Structure and Readability: Clear, well-organized code with appropriate variable names and helper functions (e.g., for time conversion).
  • Problem Decomposition: Breaking down the problem into logical sub-problems (merging, gap finding, filtering) and addressing each systematically.

Loading editor...