Frontend School

Minimize Critical Task Rescheduling

DSA
hard

Minimize Critical Task Rescheduling

Hard
Intervals
Greedy
Sorting

Overview

A global tech company manages a vast infrastructure, including critical backend services and routine system maintenance. Critical services are scheduled as tasks with specific time intervals [start, end]. Simultaneously, maintenance operations are scheduled as windows [start, end] during which servers are unavailable. Critical tasks must execute without any overlap with maintenance windows. If a critical task's original schedule [c_start, c_end] conflicts with any maintenance window, it must be shifted forward in time to the earliest possible slot where it no longer overlaps with any maintenance window. The goal is to minimize the total accumulated shift time across all critical tasks.

This problem is crucial for ensuring service uptime while efficiently managing infrastructure resources. Your solution will help optimize scheduling conflicts and minimize service disruption.

What you need to do / Task

Implement a function calculateMinShiftTime that determines the minimum total time that all critical tasks must be shifted forward to avoid conflicts with maintenance windows.

  1. Merge Maintenance Windows: First, process the maintenanceWindows to combine any overlapping or adjacent windows into a set of disjoint intervals.
  2. Calculate Shifts: For each criticalTask, determine the minimum non-negative time shift required to move it forward so that its entire duration is free from any part of any merged maintenance window.
  3. Sum Shifts: Return the sum of all individual shifts.

Input & output

Function Signature: function calculateMinShiftTime(maintenanceWindows: number[][], criticalTasks: number[][]): number

  • maintenanceWindows: An array of [start, end] pairs representing scheduled maintenance periods. Each interval [s, e] means the period from s to e (exclusive of e for duration, inclusive of s and exclusive of e for the interval itself) is unavailable. For clarity, an interval [s, e] includes time points s, s+1, ..., e-1. If a task is [0,3] and maintenance is [3,5], they do not overlap. If a task is [0,4] and maintenance is [3,5], they overlap.
  • criticalTasks: An array of [start, end] pairs representing critical service tasks. Each task [s, e] must run during this period.
  • Return: A single number representing the minimum total accumulated shift time for all critical tasks.

Clarifications

  • A task [s1, e1] and a maintenance window [s2, e2] overlap if s1 < e2 and e1 > s2. If e1 == s2 or e2 == s1, they do not strictly overlap.
  • If a critical task [c_start, c_end] needs to be shifted, it moves to [c_start + delta, c_end + delta] where delta >= 0. The goal is to find the smallest delta such that the new interval does not overlap with any maintenance window. This delta is then added to the total shift.
  • Critical tasks are independent; shifting one task does not affect the schedule or requirements of other critical tasks.
  • All interval endpoints are non-negative integers.

Examples

1

Example 1

Input:

maintenanceWindows = [[1, 5], [10, 14]], criticalTasks = [[0, 3], [4, 7], [12, 15]]

Output:

8

Note:

  1. Merged maintenance windows: [[1, 5], [10, 14]] (already disjoint).
  2. Task [0, 3] (duration 3): Initial [0, 3]. Overlaps with [1, 5]. To avoid, it must start at 5. New interval: [5, 8]. Shift = 5 - 0 = 5.
  3. Task [4, 7] (duration 3): Initial [4, 7]. Overlaps with [1, 5]. To avoid, it must start at 5. New interval: [5, 8]. Shift = 5 - 4 = 1.
  4. Task [12, 15] (duration 3): Initial [12, 15]. Overlaps with [10, 14]. To avoid, it must start at 14. New interval: [14, 17]. Shift = 14 - 12 = 2. Total shift = 5 + 1 + 2 = 8.
2

Example 2

Input:

maintenanceWindows = [[0, 2], [1, 3], [5, 7]], criticalTasks = [[0, 1], [2, 4], [6, 8]]

Output:

5

Note:

  1. Merged maintenance windows: [[0, 3], [5, 7]].
  2. Task [0, 1] (duration 1): Initial [0, 1]. Overlaps with [0, 3]. To avoid, it must start at 3. New interval: [3, 4]. Shift = 3 - 0 = 3.
  3. Task [2, 4] (duration 2): Initial [2, 4]. Overlaps with [0, 3]. To avoid, it must start at 3. New interval: [3, 5]. This new interval [3, 5] does not overlap with [5, 7] (they touch, 5 == 5). Shift = 3 - 2 = 1.
  4. Task [6, 8] (duration 2): Initial [6, 8]. Overlaps with [5, 7]. To avoid, it must start at 7. New interval: [7, 9]. Shift = 7 - 6 = 1. Total shift = 3 + 1 + 1 = 5.
3

Example 3

Input:

maintenanceWindows = [[100, 200]], criticalTasks = [[0, 50], [150, 250], [300, 350]]

Output:

50

Note:

  1. Merged maintenance windows: [[100, 200]].
  2. Task [0, 50] (duration 50): Initial [0, 50]. Does not overlap with [100, 200]. Shift = 0.
  3. Task [150, 250] (duration 100): Initial [150, 250]. Overlaps with [100, 200]. To avoid, it must start at 200. New interval: [200, 300]. Shift = 200 - 150 = 50.
  4. Task [300, 350] (duration 50): Initial [300, 350]. Does not overlap with [100, 200]. Shift = 0. Total shift = 0 + 50 + 0 = 50.

Constraints

Constraints & assumptions

  • 1 <= maintenanceWindows.length <= 2000
  • 1 <= criticalTasks.length <= 2000
  • maintenanceWindows[i].length == 2
  • criticalTasks[i].length == 2
  • 0 <= maintenanceWindows[i][0] < maintenanceWindows[i][1] <= 10^9
  • 0 <= criticalTasks[i][0] < criticalTasks[i][1] <= 10^9
  • The total accumulated shift time will fit within a standard 64-bit integer type (e.g., JavaScript number, TypeScript number which is a float but handles large integers up to 2^53).

What interviewers evaluate

  • Correctness: The solution must correctly identify all overlaps and calculate the minimum total shift time according to the problem's logic, including proper merging of intervals and handling of the shifting mechanism.
  • Efficiency: The algorithm should be optimized for the given constraints, demonstrating an understanding of time and space complexity, particularly the O(N*M) factor for interval processing.
  • Code Quality: Clean, readable, and well-structured code with appropriate data structures and clear variable names, following best practices.
  • Edge Cases: Proper handling of scenarios such as intervals that touch but don't overlap, or tasks that are already clear of maintenance windows.

Loading editor...