Об'єднати інтервали, що перетинаються · fullstack.org.ua

Об'єднати інтервали, що перетинаються

ПросунутийJavaScript

Об'єднайте всі інтервали, що перетинаються чи торкаються, в мінімальний набір непересічних інтервалів.

Напишіть функцію solve(intervals), яка приймає масив інтервалів виду [start, end] (де start ≤ end) і повертає новий масив інтервалів, у якому всі інтервали, що перетинаються чи торкаються (наприклад, [1, 4] і [4, 5]), об'єднані в один. Результат має бути відсортований за зростанням start.

Приклади

Вхід: [[1, 3], [2, 6], [8, 10], [15, 18]]

Вихід: [[1, 6], [8, 10], [15, 18]]

Вхід: [[1, 4], [4, 5]]

Вихід: [[1, 5]]

інтервали торкаються в точці 4 — вважаються перетином

Обмеження: 0 ≤ intervals.length ≤ 1000

Ваше рішення

Підказки

Підказка 1

Спершу відсортуйте інтервали за початком (start) — після цього досить одного проходу зліва направо, щоб знайти всі перетини.

Підказка 2

Порівнюйте кожен наступний інтервал з останнім доданим у результат: якщо його start не більший за end останнього — розширте останній інтервал (Math.max по end), інакше додайте новий інтервал.

Пояснення розв'язку

javascript

function solve(intervals) {
  if (intervals.length === 0) return [];

  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const result = [sorted[0]];

  for (let i = 1; i < sorted.length; i++) {
    const last = result[result.length - 1];
    const current = sorted[i];
    if (current[0] <= last[1]) {
      last[1] = Math.max(last[1], current[1]);
    } else {
      result.push(current);
    }
  }

  return result;
}