One Pager Cheat Sheet
- We can write a method that merges any overlapping meetings in a given array of time intervals with a time complexity of
O(n)
and a space complexity ofO(n)
. - Merging time ranges is relatively straightforward, as long as the intervals are properly sorted; we just need to take the smallest beginning/start time, and follow the chronological order to find the largest end/finishing time.
- We
iterate
through thesorted array
of intervals,comparing
thelast interval
andreferencing
aresult
list to store modified intervals from clear separations or overlaps.
This is our final solution.
To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.
xxxxxxxxxx
73
}
var assert = require('assert');
​
function mergeIntervals(ranges) {
ranges.sort(function (a, b) {
return a[0] - b[0] || a[1] - b[1];
});
​
let result = [],
last;
​
ranges.forEach(function (r) {
if (!last || r[0] > last[1]) {
last = r;
result.push(last);
} else if (r[1] > last[1]) last[1] = r[1];
});
​
return result;
}
​
// console.log(mergeIntervals([[1, 3], [2, 9], [3, 10], [1, 16]]))
​
try {
assertIsFunction(mergeIntervals, '`mergeIntervals` is a function');
​
console.log('PASSED: ' + '`mergeIntervals` is a function');
} catch (err) {
console.log(err);
}
​
try {
assert.deepEqual(
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
You're doing a wonderful job. Keep going!
If you had any problems with this tutorial, check out the main forum thread here.