Найдите индекс ближайшего непересекающегося интервала справа от каждого из заданных N интервалов.

Учитывая массив arr[] из N интервалов, задача состоит в том, чтобы вычислить индекс ближайшего интервала справа от каждого из заданных N интервалов, которые не перекрываются с текущим интервалом.

Примеры:

Input: arr[] = {{3, 4}, {2, 3}, {1, 2}}
Output: -1 0 1
Explanation: For the interval arr[0], there exists no interval to the right of it. For interval arr[1], i.e, [2, 3], the interval [3, 4] is the closest interval to its right that does not overlap it. Hence the required answer for arr[1] is 0. For the interval arr[2], both arr[1] and arr[2] are on its right side and does not overlap with arr[2], but arr[1] is the closest among them.

Input: arr[] = {{1, 4}, {3, 4}, {2, 3}}
Output: -1 -1 1
 

Подход: Данную задачу можно решить жадным подходом с помощью бинарного поиска. Идея состоит в том, чтобы отсортировать интервалы в порядке возрастания их начальных точек и найти ближайший интервал справа для каждого интервала. Ниже приведены шаги, которые необходимо выполнить:

• Создайте вектор пар V , хранящих начальные точки и индекс каждого интервала в arr[] .
• Отсортируйте вектор V в порядке возрастания начальных точек.
• Переберите массив arr[] и для каждого индекса найдите индекс ближайшего интервала справа, чтобы он не перекрывался с текущим интервалом, используя функцию нижней границы.

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

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