20440. 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1

문제 제목이 뭐 이래?

20440번: 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1

---

예제 입력을 보면 알 수 있듯 일명 ``겹치는 구간`` 문제이다. 선분 여러 개가 주어질 때 가장 많은 선분이 겹치는 구간을 구하는 것이다. 이 문제에서는 아래에서처럼 구간이 끝나는 즉시 또다른 선분을 통해 이어지는 상황도 고려해야 한다.

[4, 10]

이런 류의 문제는 보통 입력을 정렬한 후 우선순위 큐로 해결할 수 있다.

 

주의! 이 밑에는 치명적인 스포일러가 있습니다. 스스로 충분히 생각해 보고, 그래도 풀이가 생각나지 않을 때만 읽으세요.

정렬

나는 ``std::pair<int, int>``의 기본 정렬 순서를 사용했다. 어차피 진짜 정렬은 우선순위 큐에서 할 거라서.

우선순위 큐 (이하 pq)

pq에서는 구간의 끝이 작은 순서대로 정렬한다. 즉 먼저 끝나는 구간이 먼저 pop되도록 정렬해야 한다. 이제 위에서 정렬한 각 ``pair``마다 다음을 수행한다.

 

• pq의 top 원소의 끝나는 시간이 ``pair``의 시작하는 시간보다 커질 때까지 pq를 pop한다.
• pq에 ``pair``를 push한다.
• pq의 크기 ``size``와 지금까지 구한 정답 ``ans``를 비교한다.
  • ``size``와 ``ans``가 같을 경우, 예제 입력에서처럼 구간을 계속 이어줘야 한다.
  • ``size``가 더 클 경우에는 ``size``가 새로운 정답이 된다. 따라서 정답과 구간 모두를 갱신해야 한다.

헷갈린다면 다음의 입력을 사용하여 직접 디버깅해 보자. 디버깅도 실력이다.

6
2 16
2 3
6 10
7 10
8 10
9 10

ans
5
9 10

5
2 16
2 4
3 4
8 10
9 10

ans
3
3 4

3
2 16
4 7
6 10

ans
3
6 7

---