Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 2x 2x 2x 2x 2x 7x 2x 2x 7x 5x 5x 5x 3x 3x 3x 5x 7x 2x 2x 2x 1x 1x | // Given a list of intervals:
// [start, end].
// Find the length of the maximal set of mutually disjoint intervals.
// • Constraints:
// • 1 < N < 1e5
// • 1 ≤ A[i][0] < AÇi][1] < 1e9
// Input: [[1,2], [2, 10], [4, 6]]
// Output: 2
// Explanation:
// Select [1,2] and [4, 6].
// Selecting [2, 10] will block [1,2] and [4, 6]
const disjointInterval = (arr: number[][]): number => {
const arrSorted = arr.sort((a, b) => a[1] - b[1]);
let result = 0;
let lastInterval: number[] = [];
for (const item of arrSorted) {
if (!lastInterval.length) {
lastInterval = item;
result++;
} else {
const [start] = item;
if (start > lastInterval[1]) {
result++;
lastInterval = item;
}
}
}
return result;
};
export default disjointInterval; |