Frontend School

Identify Free Time Intervals

DSA
medium

Identify Free Time Intervals

Medium
Sorting
Intervals
Searching

Overview

In resource scheduling systems, efficiently identifying available time slots is crucial. Whether it's for booking meeting rooms, scheduling appointments, or assigning tasks, knowing when a resource is free for a specific duration is a fundamental requirement. This problem simulates a core component of such a system, focusing on how to process existing busy periods to find all contiguous free intervals that meet a minimum duration requirement within a defined operating day.

What you need to do / Task

Your task is to implement a function that takes a list of occupied time intervals, a minimum required duration, and the operating hours of a day. The function should return a list of all contiguous free time intervals that are at least the specified minimum duration long.

Specifically, you must:

  1. Consolidate Occupied Times: Process the given intervals to merge any overlapping or adjacent occupied periods into a single, non-overlapping set of busy intervals.
  2. Identify Free Gaps: Determine all time gaps that exist between the consolidated busy intervals, considering the dayStart and dayEnd boundaries.
  3. Filter by Duration: From the identified free gaps, select only those whose duration is greater than or equal to minDuration.
  4. Return Sorted Gaps: Return the filtered free time intervals, sorted by their start times.

Input & output

Your function will receive the following parameters:

  • intervals: A number[][] where each inner array [start, end] represents a time slot that is currently occupied. start and end are integers representing minutes from day 0. It is guaranteed that start < end for all given intervals.
  • minDuration: A number representing the minimum required duration (in minutes) for an available slot to be considered valid.
  • dayStart: A number representing the start time (in minutes) of the operating day.
  • dayEnd: A number representing the end time (in minutes) of the operating day.

The function should return a number[][], where each inner array [freeStart, freeEnd] represents an available time slot that meets the minDuration requirement, sorted by freeStart.

Clarifications

  • Time Units: All time values (start, end, minDuration, dayStart, dayEnd) are in minutes.
  • Operating Day: dayStart and dayEnd define the boundaries of interest. No available slots should extend before dayStart or after dayEnd.
  • Empty intervals: If the intervals array is empty, the entire period from dayStart to dayEnd should be considered available, provided its duration meets minDuration.
  • minDuration = 0: If minDuration is 0, any gap of length >= 0 should be included. Effectively, all gaps will be included.
  • Interval Endpoints: [start, end] means the interval includes start and goes up to (but not including) end. For example, [10, 15] is a 5-minute interval. An available slot [A, B] has a duration of B - A.

Examples

1

Example 1

Input:

intervals = [[30, 60], [120, 150]], minDuration = 20, dayStart = 0, dayEnd = 180

Output:

[[0,30],[60,120],[150,180]]

Note:

Given intervals are [30, 60] and [120, 150]. Day is from 0 to 180. The available gaps are [0, 30], [60, 120], and [150, 180]. All have duration >= 20.

2

Example 2

Input:

intervals = [[10, 50], [30, 70], [100, 120]], minDuration = 30, dayStart = 0, dayEnd = 150

Output:

[[70,100],[120,150]]

Note:

The input intervals are [[10, 50], [30, 70], [100, 120]]. After sorting and merging, the consolidated busy intervals are [[10, 70], [100, 120]]. Considering dayStart=0 and dayEnd=150, the potential free gaps are [0, 10] (duration 10), [70, 100] (duration 30), and [120, 150] (duration 30). With a minDuration of 30, only [70, 100] and [120, 150] are valid.

3

Example 3

Input:

intervals = [], minDuration = 60, dayStart = 480, dayEnd = 1020

Output:

[[480,1020]]

Note:

No occupied intervals. The entire day from 480 to 1020 is available. Its duration (540 minutes) is greater than or equal to minDuration (60 minutes).

4

Example 4

Input:

intervals = [[0, 1440]], minDuration = 1, dayStart = 0, dayEnd = 1440

Output:

[]

Note:

The entire operating day from 0 to 1440 is occupied by a single interval. No free slots are available.

Constraints

Constraints & assumptions

  • 0 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= intervals[i][0] < intervals[i][1] <= 1440 (representing minutes in a 24-hour day, e.g., 0 to 24*60)
  • 0 <= minDuration <= 1440
  • 0 <= dayStart < dayEnd <= 1440
  • The input intervals are not necessarily sorted.
  • Time values are integers.

Out of scope

  • Handling time zones or dates; assume all times are within a single, abstract day.
  • Complex scheduling logic beyond simple non-overlap.
  • Optimizing for multiple resources simultaneously.

What interviewers evaluate

  • Algorithmic Correctness: The solution correctly identifies all valid free time intervals, handling overlaps, boundaries, and duration filtering accurately.
  • Efficiency: The chosen approach demonstrates optimal time complexity, typically O(N log N) due to sorting, and O(N) for interval merging and gap identification.
  • Edge Case Handling: Robustness in dealing with various scenarios such as empty input, fully occupied days, or minDuration values.
  • Code Quality: Clarity, readability, and maintainability of the code, including appropriate data structures and variable naming.
  • Communication: Ability to clearly explain the thought process, chosen algorithm, and complexity analysis.

Loading editor...