Minimize Critical Task Rescheduling
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.
Implement a function calculateMinShiftTime that determines the minimum total time that all critical tasks must be shifted forward to avoid conflicts with maintenance windows.
maintenanceWindows to combine any overlapping or adjacent windows into a set of disjoint intervals.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.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.[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.[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.Examples
Example 1
Input:
maintenanceWindows = [[1, 5], [10, 14]], criticalTasks = [[0, 3], [4, 7], [12, 15]]
Output:
8
Note:
[[1, 5], [10, 14]] (already disjoint).[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.[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.[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.Example 2
Input:
maintenanceWindows = [[0, 2], [1, 3], [5, 7]], criticalTasks = [[0, 1], [2, 4], [6, 8]]
Output:
5
Note:
[[0, 3], [5, 7]].[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.[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.[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.Example 3
Input:
maintenanceWindows = [[100, 200]], criticalTasks = [[0, 50], [150, 250], [300, 350]]
Output:
50
Note:
[[100, 200]].[0, 50] (duration 50): Initial [0, 50]. Does not overlap with [100, 200]. Shift = 0.[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.[300, 350] (duration 50): Initial [300, 350]. Does not overlap with [100, 200]. Shift = 0.
Total shift = 0 + 50 + 0 = 50.Constraints
1 <= maintenanceWindows.length <= 20001 <= criticalTasks.length <= 2000maintenanceWindows[i].length == 2criticalTasks[i].length == 20 <= maintenanceWindows[i][0] < maintenanceWindows[i][1] <= 10^90 <= criticalTasks[i][0] < criticalTasks[i][1] <= 10^9number, TypeScript number which is a float but handles large integers up to 2^53).O(N*M) factor for interval processing.Loading editor...