Frontend School

Total Covered Length of Intervals

DSA
easy

Total Covered Length of Intervals

Easy
Arrays
Intervals
Sorting

Overview

Ola, as a leading ride-sharing platform, constantly optimizes driver schedules and trip assignments. A fundamental task involves understanding time segments, such as when a driver is available or when a vehicle is in use. This problem focuses on calculating the total effective duration covered by various time windows, especially when these windows might overlap. This is crucial for accurate resource allocation and operational planning.

What you need to do / Task

Your task is to implement a function that takes a list of time intervals and calculates the total length of time effectively covered by these intervals. If multiple intervals overlap, the overlapping portions should only be counted once towards the total length. Think of it as finding the length of the union of all given intervals.

Input & output

Function Signature:

function calculateTotalCoveredLength(intervals: number[][]): number
  • intervals: An array of arrays, where each inner array [start, end] represents a time interval. start and end are non-negative integers representing time points. It is guaranteed that start <= end for all intervals.
  • Returns: A single non-negative integer representing the total length of time covered by all intervals, accounting for overlaps by counting them only once.

Clarifications

  • Empty input: If the input intervals array is empty, the total covered length should be 0.
  • Single interval: If there's only one interval [s, e], the covered length is e - s.
  • Time values: All start and end values are non-negative integers. The difference end - start will also be non-negative.

Examples

1

Example 1

Input:

intervals = [[1,3],[5,7]]

Output:

4

Note:

The intervals are [1,3] and [5,7]. They do not overlap. Total length = (3-1) + (7-5) = 2 + 2 = 4.

2

Example 2

Input:

intervals = [[1,5],[3,7]]

Output:

6

Note:

The intervals [1,5] and [3,7] overlap. Their union is [1,7]. Total length = 7-1 = 6.

3

Example 3

Input:

intervals = [[1,10],[3,7],[12,15],[13,16]]

Output:

13

Note:

Intervals [1,10] contains [3,7], so they merge to [1,10]. Intervals [12,15] and [13,16] overlap, merging to [12,16]. The total covered length is (10-1) + (16-12) = 9 + 4 = 13.

Constraints

Constraints & assumptions

  • 0 <= intervals.length <= 10^4
  • 0 <= start_i <= end_i <= 10^9 for each interval [start_i, end_i]
  • The difference end_i - start_i can be up to 10^9.
  • The sum of all covered lengths can exceed the capacity of a 32-bit integer, but will fit within a 64-bit integer (standard number type in JavaScript/TypeScript).

Out of scope

  • Input validation beyond the given constraints (e.g., start > end will not occur).
  • Handling non-integer time values.

What interviewers evaluate

  • Correctness: The solution must accurately calculate the total covered length for all valid inputs, correctly handling various overlap scenarios.
  • Efficiency: The chosen algorithm should be efficient enough to handle up to 10,000 intervals with large time values, aiming for an optimal time complexity.
  • Clarity and Structure: The code should be well-organized, readable, and demonstrate a clear understanding of the problem and algorithm.

Loading editor...