Intermediate Level
Implement the mergeOverlappingIntervalsCount method that returns how many intervals remain after merging all overlaps.
The input contains a list of intervals and its length size. Each interval has a start value and an end value.
Your task is to merge all overlapping intervals and return how many intervals remain after merging. For example, [[1,3],[2,6],[8,10]] becomes [[1,6],[8,10]], so the answer is 2.
Example 1
Input
intervals (int[][]) =
[[1,3],[2,6],[8,10]]size (int) =
3Returns (int)
2Example 2
Input
intervals (int[][]) =
[[1,4],[4,5]]size (int) =
2Returns (int)
1Example 3
Input
intervals (int[][]) =
[[1,2],[3,4],[5,6]]size (int) =
3Returns (int)
3First sort the intervals by their start value.
Then process each interval in order. Keep the current merged interval. If the next interval starts before or at the current end, both intervals overlap, so extend the current end if needed. Otherwise, start a new merged interval and increase the count.
At the end, the count represents the number of intervals left after all possible merges.
Pseudocode:
function mergeOverlappingIntervalsCount(intervals, size):
if size == 0:
return 0
sort intervals by start value
count = 1
currentEnd = intervals[0][1]
for i from 1 to size - 1:
if intervals[i][0] <= currentEnd:
currentEnd = max(currentEnd, intervals[i][1])
else:
count++
currentEnd = intervals[i][1]
return countReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run