Объедините пересекающиеся интервалы

Решение

Базовая реализация

function mergeIntervals(intervals: number[][]): number[][] {
  // Если интервалов меньше 2, возвращаем как есть
  if (intervals.length <= 1) {
    return intervals;
  }

  // Сортируем интервалы по началу
  intervals.sort((a, b) => a[0] - b[0]);

  const result: number[][] = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    const current = intervals[i];
    const last = result[result.length - 1];

    // Если текущий интервал пересекается с последним, объединяем
    if (current[0] <= last[1]) {
      last[1] = Math.max(last[1], current[1]);
    } else {
      // Иначе добавляем как новый интервал
      result.push(current);
    }
  }

  return result;
}

Как это работает

Принцип работы:

1. Сортируем по началу — интервалы сортируются по первому элементу (start)
2. Инициализируем результат — первый интервал добавляем в результат
3. Итерируем оставшиеся — для каждого следующего интервала:
   • Если он пересекается с последним (current[0] <= last[1]), объединяем
   • Иначе добавляем как новый интервал
4. Обновляем конец — берём максимум из двух концов

Пошаговый процесс:

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

Шаг 1: Сортируем
  [[1,3], [2,6], [8,10], [15,18]] → уже отсортирован

Шаг 2: Инициализируем результат
  result = [[1,3]]

Шаг 3: Обрабатываем [2,6]
  current[0]=2, last[1]=3
  2 <= 3 → пересекаются
  last[1] = max(3, 6) = 6
  result = [[1,6]]

Шаг 4: Обрабатываем [8,10]
  current[0]=8, last[1]=6
  8 <= 6 → false, не пересекаются
  result.push([8,10])
  result = [[1,6], [8,10]]

Шаг 5: Обрабатываем [15,18]
  current[0]=15, last[1]=10
  15 <= 10 → false, не пересекаются
  result.push([15,18])
  result = [[1,6], [8,10], [15,18]]

Результат: [[1,6], [8,10], [15,18]]

Примеры использования

Пример 1: Пересекающиеся интервалы

mergeIntervals([[1,3], [2,6], [8,10], [15,18]]);
// [[1,6], [8,10], [15,18]]

Пример 2: Соприкасающиеся интервалы

mergeIntervals([[1,4], [4,5]]);
// [[1,5]]

Пример 3: Полностью перекрывающиеся

mergeIntervals([[1,4], [0,4]]);
// [[0,4]]

Пример 4: Вложенные интервалы

mergeIntervals([[1,5], [2,3], [4,4]]);
// [[1,5]]

Версия с проверкой пересечения функцией

function intervalsOverlap(a: number[], b: number[]): boolean {
  return a[0] <= b[1] && b[0] <= a[1];
}

function mergeIntervals(intervals: number[][]): number[][] {
  if (intervals.length <= 1) return intervals;

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

  for (let i = 1; i < intervals.length; i++) {
    const current = intervals[i];
    const last = result[result.length - 1];

    if (intervalsOverlap(last, current)) {
      last[1] = Math.max(last[1], current[1]);
    } else {
      result.push(current);
    }
  }

  return result;
}

Версия с reduce

function mergeIntervals(intervals: number[][]): number[][] {
  if (intervals.length <= 1) return intervals;

  return intervals
    .sort((a, b) => a[0] - b[0])
    .reduce((result, current) => {
      const last = result[result.length - 1];

      if (current[0] <= last[1]) {
        last[1] = Math.max(last[1], current[1]);
      } else {
        result.push(current);
      }

      return result;
    });
}

Более сложный пример с деталями

interface Interval {
  start: number;
  end: number;
  id?: string;
}

function mergeIntervalsWithMetadata(
  intervals: Interval[]
): Interval[] {
  if (intervals.length <= 1) return intervals;

  intervals.sort((a, b) => a.start - b.start);
  const result: Interval[] = [{ ...intervals[0] }];

  for (let i = 1; i < intervals.length; i++) {
    const current = intervals[i];
    const last = result[result.length - 1];

    if (current.start <= last.end) {
      // Объединяем интервалы
      last.end = Math.max(last.end, current.end);
      if (current.id) {
        last.id = `${last.id || 'merged'},${current.id}`;
      }
    } else {
      result.push({ ...current });
    }
  }

  return result;
}

// Пример:
const intervals = [
  { start: 1, end: 3, id: 'A' },
  { start: 2, end: 6, id: 'B' },
  { start: 8, end: 10, id: 'C' }
];

mergeIntervalsWithMetadata(intervals);
// [
//   { start: 1, end: 6, id: 'A,B' },
//   { start: 8, end: 10, id: 'C' }
// ]

Тестирование

import { describe, it, expect } from 'vitest';

describe('mergeIntervals', () => {
  it('должен объединить пересекающиеся интервалы', () => {
    const result = mergeIntervals([[1,3], [2,6], [8,10], [15,18]]);
    expect(result).toEqual([[1,6], [8,10], [15,18]]);
  });

  it('должен объединить соприкасающиеся интервалы', () => {
    const result = mergeIntervals([[1,4], [4,5]]);
    expect(result).toEqual([[1,5]]);
  });

  it('должен объединить вложенные интервалы', () => {
    const result = mergeIntervals([[1,4], [0,4]]);
    expect(result).toEqual([[0,4]]);
  });

  it('должен обработать пустой массив', () => {
    const result = mergeIntervals([]);
    expect(result).toEqual([]);
  });

  it('должен обработать один интервал', () => {
    const result = mergeIntervals([[1,5]]);
    expect(result).toEqual([[1,5]]);
  });

  it('должен обработать не пересекающиеся интервалы', () => {
    const result = mergeIntervals([[1,2], [3,4], [5,6]]);
    expect(result).toEqual([[1,2], [3,4], [5,6]]);
  });

  it('должен обработать вложенные интервалы', () => {
    const result = mergeIntervals([[1,5], [2,3], [4,4]]);
    expect(result).toEqual([[1,5]]);
  });

  it('должен обработать неотсортированные интервалы', () => {
    const result = mergeIntervals([[8,10], [2,6], [1,3], [15,18]]);
    expect(result).toEqual([[1,6], [8,10], [15,18]]);
  });
});

Анализ сложности

Временная сложность:

• Сортировка: O(n log n)
• Итерация: O(n)
• Итого: O(n log n)

Пространственная сложность:

• Результат: O(n) в худшем случае (нет пересечений)
• Итого: O(n)

Практические применения

1. Расписания и занятость:

const busyHours = [[9,11], [13,15], [14,16], [17,19]];
const merged = mergeIntervals(busyHours);
// [[9,11], [13,16], [17,19]]
// Найти свободное время

2. Диапазоны IP адресов:

const ipRanges = [
  [192168000001, 192168000255],
  [192168001000, 192168001255],
  [192168002000, 192168002255]
];
const merged = mergeIntervals(ipRanges);

3. Сегменты видео:

const subtitles = [
  [0, 5000],    // 0-5 сек
  [4000, 8000], // 4-8 сек
  [10000, 15000] // 10-15 сек
];
const merged = mergeIntervals(subtitles);
// [[0, 8000], [10000, 15000]]

4. Резервирование номеров:

const reservations = [
  [2024010101, 2024010105],
  [2024010104, 2024010108],
  [2024010110, 2024010115]
];
const merged = mergeIntervals(reservations);
// [[2024010101, 2024010108], [2024010110, 2024010115]]

Альтернативные подходы

Подход с событиями (событие start/end):

function mergeIntervalsWithEvents(intervals: number[][]): number[][] {
  const events: [number, 'start' | 'end'][] = [];

  intervals.forEach(([start, end]) => {
    events.push([start, 'start']);
    events.push([end, 'end']);
  });

  events.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : a[1] === 'start' ? -1 : 1);

  const result: number[][] = [];
  let count = 0;
  let start = 0;

  for (const [time, type] of events) {
    if (type === 'start') {
      if (count === 0) start = time;
      count++;
    } else {
      count--;
      if (count === 0) result.push([start, time]);
    }
  }

  return result;
}

Этот подход работает за O(n log n) и может быть полезен, если нужны дополнительные метаданные.