Минимизируйте группу так, чтобы никакие два диапазона одной и той же группы не пересекались

Дан массив ranges[] размера N (1 ≤ N ≤ 10 ⁵ ), где ranges[i] = {start _i , end _i } представляет собой диапазон между start _i и end _i (оба включительно). Задача состоит в том, чтобы найти минимальное количество необходимых групп, чтобы каждый интервал of ranges[] принадлежит ровно одной группе, и никакие два ranges[i] в одной и той же группе не пересекаются друг с другом.

Примечание. Два интервала пересекаются, если между ними существует хотя бы одно общее число. Например, интервалы [2, 6] и [6, 7] пересекаются.

Примеры:

Input: ranges[] = {{5, 10}, {6, 8}, {1, 5}, {2, 3}, {1, 10}}
Output: 3
Explanation: We can divide the range[] into the following groups:
Group 1: {1, 5}, {6, 8}.
Group 2: {2, 3}, {5, 10}.
Group 3: {1, 10}.

Input: ranges[] = {{1, 3], {5, 6}, {8, 10}, {11, 13}}
Output: 1

Подход с использованием линейной развертки:

The idea is to keep track of maximum number of overlapping intervals at any time say N. So there should be N numbers of individual groups to avoid any intersection internally in group.

Выполните следующие шаги, чтобы реализовать вышеуказанную идею:

• Инициализировать карту, чтобы сохранить диапазоны в отсортированном порядке на основе начального диапазона
• Инициализируйте результат переменной, чтобы представить максимальное количество перекрывающихся интервалов.
• Итерация по каждому диапазону диапазонов[]
  • Увеличьте количество вхождений диапазона на карте
• Инициализировать переменную sum для представления количества диапазонов, которые перекрываются в определенное время.
• Перебрать карту и вычислить сумму префиксов появления диапазона
  • Максимизируйте результат с максимальным количеством интервалов, которые перекрываются в определенное время
• Вернуть результат

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)