Let's start with the description for .
🔧 Programmierung 🕛 vor 1 Jahr 3 Min Lesezeit
LeetCode Meditations: Merge Intervals
If they don't overlap, we can just add that interval to result. Otherwise, we need to update the "last end," effectively merging the intervals:
CODE
for (const interval of intervals) {
const [currentStart, currentEnd] = [interval[0], interval[1]];
// non-overlapping
if (result[result.length - 1][1] < currentStart) {
result.push(interval);
// overlapping, update last end
} else {
result[result.length - 1][1] = Math.max(result[result.length - 1][1], currentEnd);
}
}
And, the only thing left to do is to return the result:
CODE
function merge(intervals: number[][]): number[][] {
/* ... */
return result;
}
And, this is how our final solution looks like in TypeScript:
CODE
function merge(intervals: number[][]): number[][] {
intervals.sort((a, b) => a[0] - b[0]);
let result = [intervals[0]];
for (const interval of intervals) {
const [currentStart, currentEnd] = [interval[0], interval[1]];
// non-overlapping
if (result[result.length - 1][1] < currentStart) {
result.push(interval);
// overlapping, update last end
} else {
result[result.length - 1][1] = Math.max(result[result.length - 1][1], currentEnd);
}
}
return result;
}
Time and space complexity
We are sorting intervals, and the built-in sort function has
O(n log n)O(n \ log \ n) O(n log n)
time complexity. (The looping is
O(n)O(n) O(n)
, but the overall time complexity is
O(n log n)O(n \ log \ n) O(n log n)
).
The result array can increase in size as the size of the input array intervals increases, therefore we have
O(n)O(n) O(n)
space complexity.
Next up, we'll take a look at the last problem in the chapter, Non-overlapping Intervals. Until then, happy coding.
Vollständiger Original-Bericht
Ausführliche Details, Code-Beispiele & Hersteller-Stellungnahme auf dev.to.
SOCIAL SHARE CARD GENERATOR