강의실 배정 11000

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

시간복잡도 O(NlogN)

반례
8
5 6
3 7
1 8
8 10
6 11
11 12
10 14
9 16

3

을 가지고 그림을 그리면서 이해해보려고 하였다
밑의 그림은 시작시간 기준으로 오름차순 정렬 같으면 마치는 시간 오름차순 정렬한것과
마치는 시간 오름차순정렬 같으면 시작시간 오름차순 정렬한 것이다

시작시간 오름차순 정렬. 같은 경우 마치는시간 오름차순 정렬후
강의실 넣을때는 마치는시간 오름차순으로 배정 결과 강의실 3개

마치는시간 오름차순 정렬. 같은 경우 시작시간 오름차순 정렬후
강의실 넣을때는 마치는시간 내림차순 정렬 배정 결과 강의실 4개
답도 틀리고 이 방식에 문제가 있는게 마치는시간 내림차순 정렬이다 보니 while문으로 원소들을 탐색해서 다음것과 시간 비교를 계속 해줘야해서 비용이 크다 생각보다

유용했던 반례모음
4
1 3
2 3
3 7
6 7

2

8
5 6
3 7
1 8
8 10
6 11
11 12
10 14
9 16

3

5
1 7
2 3
3 4
4 8
7 10

2

7
1 3
2 4
3 5
1 7
5 7
4 4
4 4

3

import java.io.*;
import java.util.*;

class Lec
{
    int s;
    int e;

    public Lec(int s, int e) {
        this.s = s;
        this.e = e;
    }
}

public class Main
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());//1 ~ 200000

        ArrayList<Lec> lecList = new ArrayList<>();

        String[] input;
        for(int i = 0; i < N; ++i)
        {
            input = br.readLine().split(" ");
            int s = Integer.parseInt(input[0]);//0 ~ 10^9
            int e = Integer.parseInt(input[1]);//s ~ 10^9
            lecList.add(new Lec(s, e));
        }

        Comparator<Lec> comparator = new Comparator<Lec>() {
            @Override
            public int compare(Lec a, Lec b) {
                if(a.s != b.s)
                    return a.s < b.s ? -1 : 1;
                else
                    return a.e < b.e ? -1 : 1;
            }
        };

        Collections.sort(lecList, comparator);

        PriorityQueue<Lec> roomList = new PriorityQueue<>(new Comparator<Lec>() {
            @Override
            public int compare(Lec a, Lec b) {
                if(a.e != b.e)
                    return a.e < b.e ? -1 : 1;
                else
                    return a.s < b.s ? -1 : 1;
            }
        });
        roomList.add(new Lec(0, 0));

        for(Lec cur : lecList)
        {
            if (cur.s >= roomList.peek().e) {
                roomList.poll();
            }
            roomList.add(cur);
        }

        System.out.println(roomList.size());
    }
}