Count Integers Covered by Merged Intervals
Problem statement
You are given a list intervals, where intervals[i] = [start_i, end_i]. Each interval covers every integer x with start_i <= x <= end_i, so both ends are included.
Merge the overlapping intervals and return how many different integers the merged intervals cover. In other words, count the integers that lie in at least one interval.
- The intervals can come in any order. They may overlap, sit inside each other, share an endpoint, or repeat.
- An integer that lies in several intervals is counted once.
Function
countCoveredIntegers(intervals: int[][]) → intExamples
Example 1
intervals = [[1,3],[5,6]]return = 5The first interval covers 1, 2, 3 and the second covers 5, 6. They do not overlap, so 3 + 2 = 5 integers are covered.
Example 2
intervals = [[2,6],[1,3],[8,10],[9,9]]return = 9Sorted by start, [1,3] and [2,6] overlap and merge into [1,6], which covers 6 integers. [9,9] lies inside [8,10], which covers 3 integers. The total is 6 + 3 = 9.
Example 3
intervals = [[1,4],[4,7]]return = 7Both intervals contain 4. The covered integers are 1 through 7, so the answer is 7, not 8: the shared integer is counted once.
Constraints
1 <= intervals.length <= 10^4intervals[i].length == 20 <= start_i <= end_i <= 10^9