Mastery Points
0
Merge Overlapping Intervals in dsa
Context & Logic
Merge Intervals involves combining overlapping ranges of numbers. This is a common problem solved by first sorting the intervals based on their start times.
Example
function merge(intervals) {
if (!intervals.length) return [];
intervals.sort((a, b) => a[0] - b[0]);
const result = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
let last = result[result.length - 1];
if (intervals[i][0] <= last[1]) {
last[1] = Math.max(last[1], intervals[i][1]);
} else {
result.push(intervals[i]);
}
}
return result;
}Step-by-Step Logic
1
Sort the intervals based on start time.
2
Initialize an empty merged list and add the first interval.
3
Iterate through the remaining intervals.
4
If current interval overlaps with the last merged interval, update the end time.
5
If not, add the current interval to the merged list.
Complexity Metrics
Time Efficiency
O(n log n) due to sorting
Memory Footprint
O(n) for the output