스위핑

핵심포인트

1. a,b 각 구간마다 오름차순으로 정렬하고 리스트에 넣기.
2. 팀소트로 구간정렬하기.
3. 정렬기준은 구간 중복 횟수가 중점이면 b를 기준으로, 길이가 중점이면 a를 기준으로 정렬한다.
4. 긴 구간을 2순위로 정렬 조건에 추가한다. (a,-b) 또는 (b,-a) 이렇게 하면 정렬 후 연산을 조금이라도 줄여준다.

li.sort(key = lambda x : (x[0],-x[1]))

5. 만약 한번에 처리가능한 구간단위가 별도로 주어진다면 반복문에서 현재 구간의 길이와 비교해서 무시하든지 요구사항에 맞게 처리한다. (https://www.acmicpc.net/problem/1911)
6. 중복 구간 횟수를 카운트할 때는 우선순위큐를 적극 이용한다.

실습

우선순위 큐를 활용한 범위 내의 완전히 겹치는 구간의 합 구하기.
https://www.acmicpc.net/problem/13334

https://www.acmicpc.net/problem/2170