Задача: 757. Set Intersection Size At Least Two
Сложность: hard

Вам дан двумерный целочисленный массив intervals, в котором intervals[i] = [starti, endi] представляет все целые числа от starti до endi включительно. Содержащее множество - это массив nums, в котором каждый интервал из intervals содержит не менее двух целых чисел в nums. Например, если intervals = [[1,3], [3,7], [8,9]], то [1,2,4,7,8,9] и [2,3,4,8,9] - содержащие множества. Верните минимально возможный размер содержащего множества.

Пример:

Input: intervals = [[1,3],[3,7],[8,9]]
Output: 5

👨‍💻 Алгоритм:

1⃣Отсортируйте интервалы по их конечным точкам.

2⃣Инициализируйте пустое множество для хранения чисел.

3⃣Пройдите по каждому интервалу, добавляя необходимые числа в множество так, чтобы каждый интервал содержал не менее двух чисел из этого множества.

😎 Решение:

function minSetSize(intervals) {
    intervals.sort((a, b) => a[1] - b[1]);
    let nums = [];
    for (let [start, end] of intervals) {
        if (nums.length === 0 || nums[nums.length - 1] < start) {
            nums.push(end - 1);
            nums.push(end);
        } else if (nums[nums.length - 1] === end - 1) {
            nums.push(end);
        }
    }
    return nums.length;
}

Ставь 👍 и забирай 📚 Базу знаний