Подсчитайте количество точек пересечения для заданных линий между (i, 0) и (j, 1)

Учитывая массив, lines[] из N пар формы (i, j), где (i, j) представляет собой отрезок от координаты (i, 0) до (j, 1) , задача состоит в том, чтобы найти количество точки пересечения данных прямых.

Пример:

Input: lines[] = {{1, 2}, {2, 1}}
Output: 1
Explanation: For the given two pairs, the line form (1, 0) to (2, 1) intersect with the line from (2, 0) to (1, 1) at point (1.5, 0.5). Hence the total count of points of intersection is 1.

Input: lines[] = {{1, 5}, {2, 1}, {3, 7}, {4, 1}, {8, 2}}
Output: 5

Подход: Данная проблема может быть решена с использованием жадного подхода с использованием структуры данных на основе политик. Можно заметить, что для линий, представленных b, две пары (a, b) и (c, d) должны пересекаться либо (a > c и b < d) , либо (a < c и b > d) .

Следовательно, используя это наблюдение, данный массив пар можно отсортировать по убыванию 1 ^-го элемента. При обходе массива вставьте значение второго элемента в структуру данных на основе политики и найдите количество элементов, меньшее, чем второй элемент вставленной пары, с помощью функции order_of_key и сохраните сумму количества в переменной. Аналогично вычислить случаи после сортировки заданного массива пар в порядке убывания их 2- ^го элемента.

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

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