Mam więc zestaw zawierający punkty końcowe interwałów. Na przykład,

Set s = {(1,4),(3,7),(5,8),(14,17),(0,2),(11,14)}

Potrzebuję sposobu, aby dowiedzieć się, ile jest nakładających się interwałów. W powyższym przypadku odpowiedź będzie wynosić 5 od

(1,4) --> (3,7), (0,2)
(3,7) --> (5,8),(0,2)
(5,8) --> 
(14,17) --> (11,14)

Potrzebuję algorytmuO(N log N) czas, aby dowiedzieć się sumy. Teraz, jeśli posortuję wszystkie punkty początkowe i zastosuję sugerowaną tu odpowiedź w każdym punkcieZnajdź skrzyżowanie zakresu numerów Dostaję rozwiązanie O (N ^ 2). Jakieś wskazówki na temat tego, jakiej struktury danych potrzebuję oprócz zestawu? Dzięki!