안녕하세요. 풀다가 막혀서 질문 드립니다.

제가 푼 방식은

우선 N이 500이기때문에, 입력받은 숫자들을 기준점으로 plane sweep 비스무리한 방식으로 푸는 중입니다.

문제는 아래와 같이 범위가 겹치는 부분이더라구요.

3

1 500

300 700

500 900

라는 input이 들어왔을때 0, 1, 300, 500, 700 , 900을 기준으로 계산을 합니다.

1. 서로 겹치지 않는 부분은 앞의숫자 범위 * 뒤의 숫자 범위로 간단히 경우의 수가 계산되죠.

위의 예로 들면 (299-1)*(499-301+1)*(900-500+1) 은 쉽게 계산되는 경우의 수 입니다.

2. 문제는 겹치는 범위입니다.

첫번째 학교에서 300~500 사이의 값을 선택한다면, 두번쨰 학교는 (700-(첫번째학교+1))을 선택해야하고 

마찬가지로 세번째학교도 두번째 학교에서 500이 넘는 값을 선택했다면 (900-(첫번째학교+1)) 이 들어와야하죠. 

선택안하는 경우의 수는 별도로 하구요.

이렇게 생각을 하다보니, plane sweep 방법을 사용할 수가 없겠더라구요.

이런 문제는 어떤방향으로 접근해야하는지 조금만 조언해주시면 감사하겠습니다.