Если ответом для первого абзаца является набор интервалов, то посмотрите на структуры данных дерева диапазонов и дерева интервалов и игнорируйте остальное, что я должен сказать.
Если ответом для первого абзаца является простой подсчет, то дерево диапазонов и дерево интервалов - это не то, что вам нужно, потому что стоимость поиска там растет с количеством найденных пересекающихся интервалов. Однако обратите внимание, что если i j, вы все равно увидите совпадение. Это означает, что полученный вами ответ не зависит от порядка, в котором вы представляете интервалы, поэтому вы можете выбрать его для себя.
Отсортируйте интервалы в порядке возрастания первой координаты и работайте через них один за другим, сохраняя при этом очередь просматриваемых до сих пор интервалов, упорядочив их по убыванию второй координаты. Когда вы видите новый интервал, удалите из очереди все ранее видимые интервалы, имеющие вторую координату, что означает, что он не пересекается с новым интервалом. Новый интервал будет пересекаться со всем остальным, поэтому накапливайте количество найденных пересечений, добавляйте новый интервал в очередь и продолжайте.
Это дает вам счетчик количества пересечений во времени n log n. Если вы хотите количество непересекающихся, вычтите это из n (n-1) /2.