Frontend School

Longest K-Concurrent Outage Period

DSA
hard

Longest K-Concurrent Outage Period

Hard
Intervals
Sweep Line
Arrays
Sorting

Overview

Postman relies on highly available services. When multiple services experience outages simultaneously, it can lead to critical system failures. This problem asks you to identify the longest continuous time window during which at least k distinct services were concurrently unavailable. This is crucial for understanding the impact of cascading failures and for post-incident analysis.

What you need to do / Task

Implement the function findLongestKOverlapPeriod that takes a list of service outage intervals and an integer k, and returns the length of the longest time period where at least k services were simultaneously experiencing an outage.

Input & output

  • outages: An array of number[] representing service outage intervals. Each inner array [start, end] denotes an outage from start time to end time (inclusive of start, exclusive of end). start < end is guaranteed.
  • k: A positive integer representing the minimum number of concurrent outages required.

Returns: A number representing the length of the longest period where at least k services were simultaneously down. If no such period exists, return 0.

Clarifications

  • An interval [start, end] means the service is down for the duration [start, end). The time end itself is when the service becomes available again. The length of such an interval is end - start.
  • If k=1, you're looking for the longest single outage period (which might be a merged one if multiple outages form a continuous block).
  • Time points are non-negative integers.
  • The problem specifically asks for the longest consecutive period, not the sum of all periods meeting the criteria.

Examples

1

Example 1

Input:

outages = [[1, 5], [3, 7], [2, 6], [8, 10], [9, 12]], k = 2

Output:

4

Note:

Intervals: [1,5), [2,6), [3,7), [8,10), [9,12).

  • At time 1: 1 outage ([1,5))
  • At time 2: 2 outages ([1,5), [2,6)). Count becomes >= k. Start k-overlap period at 2.
  • At time 3: 3 outages ([1,5), [2,6), [3,7)). Count is >= k.
  • At time 5: 2 outages ([2,6), [3,7)). Count is >= k.
  • At time 6: 1 outage ([3,7)). Count drops below k. End k-overlap period at 6. Length = 6 - 2 = 4. Max length becomes 4.
  • At time 7: 0 outages.
  • At time 8: 1 outage ([8,10)).
  • At time 9: 2 outages ([8,10), [9,12)). Count becomes >= k. Start k-overlap period at 9.
  • At time 10: 1 outage ([9,12)). Count drops below k. End k-overlap period at 10. Length = 10 - 9 = 1. Max length remains 4. The longest period is 4.
2

Example 2

Input:

outages = [[10, 20], [15, 25], [30, 40]], k = 3

Output:

0

Note:

Even though outages exist, at no point do 3 or more services concurrently experience an outage. The maximum concurrent outages is 2 (between time 15 and 20).

3

Example 3

Input:

outages = [[1, 10], [1, 5], [6, 10]], k = 1

Output:

9

Note:

Intervals: [1,10), [1,5), [6,10).

  • At time 1: 2 outages ([1,10), [1,5)). Count becomes >= k. Start k-overlap period at 1.
  • At time 5: 1 outage ([1,10), [6,10) is not active yet). Count is >= k.
  • At time 6: 2 outages ([1,10), [6,10)). Count is >= k.
  • At time 10: 0 outages. Count drops below k. End k-overlap period at 10. Length = 10 - 1 = 9. Max length becomes 9. The longest period is 9.

Constraints

Constraints & assumptions

  • 0 <= outages.length <= 10^5
  • Each outage interval [start, end] will have 0 <= start < end <= 10^9.
  • 1 <= k <= outages.length (If outages.length is 0, k will be ignored, and the function should return 0).
  • The outages array may not be sorted.

Out of scope

  • Handling invalid interval formats (e.g., start >= end). Assume valid input as per constraints.
  • Optimizations for extremely sparse or extremely dense time ranges beyond the standard sweep-line approach.

What interviewers evaluate

  • Algorithmic Correctness: Ability to correctly identify and implement a sweep-line algorithm for interval processing.
  • Edge Case Handling: Correctly managing scenarios like empty input, k=1, intervals of zero length (e.g., [5,5], though constrained to start < end), or no periods meeting the k criteria.
  • Time & Space Efficiency: Optimal use of data structures and algorithms (expected O(N log N) time, O(N) space where N is outages.length).
  • Code Clarity & Structure: Well-organized, readable code with appropriate variable names and comments.

Loading editor...