x축만 있는 선분 n개의 시작점과 끝점이 주어졌을때
각각의 선분이 몇개의 선분과 겹치는지 구해야 되는데
시작점을 기준으로 오름차순으로 정렬해서 해당 선분의 시작점과 끝점에 다음 선분의 시작점이 들어오는지만 체크하면
되는건가요
x축만 있는 선분 n개의 시작점과 끝점이 주어졌을때
각각의 선분이 몇개의 선분과 겹치는지 구해야 되는데
시작점을 기준으로 오름차순으로 정렬해서 해당 선분의 시작점과 끝점에 다음 선분의 시작점이 들어오는지만 체크하면
되는건가요
내가 지금 머리가 잘 안돌아가서 세그트리 쓰는 N lg N 밖에 생각이 안남 혹시 정렬되어있을 때 O(N) 아시는분?
세그먼트트리로 구현하면 1~n번까지 선분을 맨 마지막 바닥 노드에 놓고 1:2 노드에다가 1번,2번 선분 겹치는지 확인하고 이런식으로 가는거야?