Frontend School

Max Scheduled Maintenance Slots

DSA
medium

Max Scheduled Maintenance Slots

Medium
Intervals
Greedy
Sorting

Overview

Apple's content delivery network (CDN) needs to efficiently schedule maintenance windows for its global server infrastructure. Each server has specific time slots when it's available for maintenance. To minimize disruption and ensure critical updates are applied, we need to select the maximum number of non-overlapping maintenance slots, with an additional constraint: each chosen slot must meet a minimum required duration to be effective.

What you need to do / Task

Implement a function maxScheduledMaintenanceSlots that takes a list of available maintenance time slots and a minimum required duration. Your function should return the maximum number of non-overlapping maintenance slots that can be scheduled, where each selected slot has a duration equal to or greater than the specified minimum.

Input & output

The function maxScheduledMaintenanceSlots takes two arguments:

  • intervals: An array of arrays, where each inner array [start, end] represents an available maintenance time slot. start and end are integers representing timestamps. start < end is guaranteed.
  • minDuration: An integer representing the minimum required duration for a maintenance slot to be considered valid.

The function should return an integer, representing the maximum number of non-overlapping maintenance slots that satisfy the minDuration constraint.

Clarifications

  • Empty input: If intervals is empty, return 0.
  • Invalid duration: If minDuration is non-positive, treat it as 1 for filtering purposes.
  • Interval format: All intervals [start, end] are inclusive of start and exclusive of end. The duration of an interval [start, end] is end - start.
  • Non-overlapping: Two intervals [a, b] and [c, d] are non-overlapping if b <= c or d <= a.

Examples

1

Example 1

Input:

intervals = [[1, 4], [2, 5], [7, 9], [3, 8]], minDuration = 2

Output:

2

Note:

  1. Filtered by minDuration >= 2: [[1, 4], [2, 5], [7, 9], [3, 8]]. All intervals have duration >= 2.
  2. Sort by end time: [[1, 4], [2, 5], [3, 8], [7, 9]].
  3. Select [1, 4]. Count = 1. Last end time = 4.
  4. [2, 5] overlaps with [1, 4]. Skip.
  5. [3, 8] overlaps with [1, 4]. Skip.
  6. [7, 9] does not overlap with [1, 4] (7 >= 4). Select [7, 9]. Count = 2. Last end time = 9. Maximum 2 non-overlapping slots.
2

Example 2

Input:

intervals = [[1, 2], [2, 3], [3, 4]], minDuration = 1

Output:

3

Note:

  1. Filtered by minDuration >= 1: [[1, 2], [2, 3], [3, 4]]. All intervals have duration 1.
  2. Sort by end time: [[1, 2], [2, 3], [3, 4]].
  3. Select [1, 2]. Count = 1. Last end time = 2.
  4. [2, 3] does not overlap with [1, 2] (2 >= 2). Select [2, 3]. Count = 2. Last end time = 3.
  5. [3, 4] does not overlap with [2, 3] (3 >= 3). Select [3, 4]. Count = 3. Last end time = 4. Maximum 3 non-overlapping slots.
3

Example 3

Input:

intervals = [[1, 5], [2, 3], [4, 6]], minDuration = 3

Output:

1

Note:

  1. Filtered by minDuration >= 3:
    • [1, 5] (duration 4 >= 3) -> Keep
    • [2, 3] (duration 1 < 3) -> Discard
    • [4, 6] (duration 2 < 3) -> Discard Filtered list: [[1, 5]].
  2. Sort by end time: [[1, 5]].
  3. Select [1, 5]. Count = 1. Last end time = 5. Maximum 1 non-overlapping slot.

Constraints

Constraints & assumptions

  • 0 <= intervals.length <= 10^5
  • intervals[i].length == 2
  • 0 <= start < end <= 10^9 for each [start, end] in intervals.
  • 1 <= minDuration <= 10^9 (after accounting for non-positive minDuration as 1).
  • The input intervals are not necessarily sorted.

What interviewers evaluate

  • Algorithmic efficiency: Solution should be optimal in terms of time and space complexity for the given constraints.
  • Correctness: Handles edge cases and adheres to all problem constraints and definitions.
  • Code quality: Clean, readable, and well-structured code with appropriate variable names.
  • Problem decomposition: Ability to break down the problem into logical steps (e.g., filtering, sorting, greedy selection).

Loading editor...