Frontend School

Find Available Service Slots

DSA
medium

Find Available Service Slots

Medium
Intervals
Greedy
Arrays

Overview

Urban Company relies on efficient scheduling to connect customers with service partners. Each partner has a daily schedule, which includes pre-booked appointments or personal commitments. To facilitate new service bookings, the system needs to quickly identify available time windows where a partner can take on a new service request of a specific duration.

This problem asks you to implement a function that, given a partner's busy schedule for a day and a required service duration, finds all contiguous time slots that are free and long enough to accommodate the service.

What you need to do / Task

Implement the findAvailableSlots function that:

  1. Takes a list of busyIntervals representing a partner's occupied time during a day.
  2. Takes a serviceDuration representing the minimum length of an available slot needed.
  3. Returns a list of all free time intervals that are at least serviceDuration long.

Input & output

Function Signature:

function findAvailableSlots(busyIntervals: number[][], serviceDuration: number): number[][]

Parameters:

  • busyIntervals: An array of number[] arrays, where each inner array [start, end] represents a time interval in minutes from midnight (e.g., [0, 60] means 12:00 AM to 1:00 AM). These intervals are guaranteed to be non-overlapping and sorted by their start times.
  • serviceDuration: A number representing the minimum duration (in minutes) required for a service slot. This value will always be positive.

Return Value:

  • An array of number[] arrays, where each inner array [start, end] represents an available time slot. The returned intervals must be sorted by their start times and each must have a duration of at least serviceDuration. If no such slots exist, return an empty array.

Clarifications

  • Time Representation: All times are in minutes from midnight. The day starts at 0 minutes (12:00 AM) and ends at 1440 minutes (12:00 AM the next day, exclusive). So, a full day is [0, 1440).
  • Non-overlapping intervals: The busyIntervals provided will not overlap. For example, [[60, 120], [90, 150]] is not a valid input because [60, 120] and [90, 150] overlap. The input intervals are also sorted by their start times.
  • Empty busyIntervals: If busyIntervals is empty, it means the partner has no scheduled commitments for the day.
  • serviceDuration: Will always be a positive integer.

Examples

1

Example 1

Input:

busyIntervals = [[480, 540], [600, 660]], serviceDuration = 30

Output:

[[0,480],[540,600],[660,1440]]

Note:

Partner is busy from 8:00 AM to 9:00 AM (480-540) and 10:00 AM to 11:00 AM (600-660). Free slots are [0, 480], [540, 600], [660, 1440]. All are longer than or equal to 30 minutes.

2

Example 2

Input:

busyIntervals = [[0, 1440]], serviceDuration = 60

Output:

[]

Note:

The partner is busy for the entire day. No available slots of any duration.

3

Example 3

Input:

busyIntervals = [], serviceDuration = 120

Output:

[[0,1440]]

Note:

The partner has no busy intervals, so the entire day is free. This slot [0, 1440] is longer than 120 minutes.

4

Example 4

Input:

busyIntervals = [[60, 90], [120, 150]], serviceDuration = 60

Output:

[[0,60],[150,1440]]

Note:

Free slots are [0,60], [90,120], [150,1440]. The slot [90,120] (30 mins) is too short for a 60-minute service. So only [0,60] and [150,1440] are returned.

Constraints

Constraints & assumptions

  • 0 <= busyIntervals.length <= 10^5
  • Each busyInterval is [start, end] where 0 <= start < end <= 1440.
  • busyIntervals are non-overlapping and sorted by their start times.
  • 1 <= serviceDuration <= 1440
  • All times are integers.

What interviewers evaluate

  • Correctness: The solution accurately identifies all valid available slots, handling edge cases like empty schedules or schedules covering the entire day.
  • Efficiency: The algorithm processes the intervals with optimal time and space complexity.
  • Code Structure & Readability: The code is well-organized, easy to understand, and follows standard coding practices.
  • Problem-solving approach: Demonstrates a clear thought process, including identifying sub-problems and choosing appropriate data structures/algorithms.

Loading editor...