회의실 배정 1931

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

처음엔 끝나는 시간을 기준으로 정렬해서 제출했는데 IllegalArgumentException 이 떳다
한참 구글링해서 찾다보니 compareTo 함수에서 Meeting객체의 end가 같은경우에 대한 처리가 없어서 발생한 것이었다

@Override
    public int compareTo(Meeting o) {
        return (this.end < o.end) ? -1:1;
    }

그래서 다음 코드처럼 수정해서 제출했더니 이번에는 틀렸다고 한다

@Override
    public int compareTo(Meeting o) {
        return (this.end <= o.end) ? -1:1;
    }

그래서 질문게시판을 찾아보았고 틀린부분을 알게되었다. 회의 마치는 시간이 같은경우에 시작시간을 기준으로 오름차순으로 정렬해야한다.
그러지 않을 경우 다음 그림의 경우 답이 2개만 나온다 3개나와야 하는데

마치는 시간이 같을 경우 시작시간을 기준으로 오름차순 정렬한뒤에
앞선 회의의 마치는 시간과 현재회의의 시작시간을 비교해서 처리하면 답이 3개가 나온다

시간복잡도 O(N)
100000

반례
3
3 3
1 3
3 3
답3

시작시간 오름차순 정렬. 같은 경우 마치는 시간 오름차순 정렬

마치는 시간 오름차순 정렬. 같은 경우 시작시간 오름차순 정렬

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

class Meeting implements Comparable<Meeting>
{
    int start;
    int end;

    public Meeting(int start, int end) {
        this.start = start;
        this.end = end;
    }

    @Override
    public int compareTo(Meeting o) {
        if(this.end != o.end)
            return (this.end < o.end) ? -1:1;
        else
            return (this.start <= o.start) ? -1:1;
    }
}

public class Main
{
    static BufferedReader br;

    static int N;

    static Meeting[] arr;

    static Stack<Meeting> stack = new Stack<>();

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

        N = Integer.parseInt(br.readLine());
        arr = new Meeting[N];

        String[] input;

        for(int i = 0; i < N; ++i)
        {
            input = br.readLine().split(" ");

            arr[i] = new Meeting(Integer.parseInt(input[0]), Integer.parseInt(input[1]));
        }

        Arrays.sort(arr);

        stack.push(arr[0]);
        for(int i = 1; i < arr.length; ++i)
        {
            if(stack.peek().end > arr[i].start)
                continue;

            stack.push(arr[i]);
        }

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

두번째 풀이
방법은 같고 우선순위큐로 풀었다

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

class Meeting implements Comparable<Meeting>
{
    int st;
    int ed;

    public Meeting(int st, int ed) {
        this.st = st;
        this.ed = ed;
    }

    @Override
    public int compareTo(Meeting o)
    {
        if(this.ed != o.ed)
            return this.ed - o.ed < 0 ? -1:1;
        else {
            return this.st - o.st < 0 ? -1:1;
        }
    }
}

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~100000
        String[] input;

        PriorityQueue<Meeting> pq = new PriorityQueue<>();

        for(int i = 0; i < N; ++i)
        {
            input = br.readLine().split(" ");

            int st = Integer.parseInt(input[0]);// 0 ~ 2^31-1
            int ed = Integer.parseInt(input[1]);

            pq.add(new Meeting(st, ed));
        }

        int end = 0;
        int ans = 0;
        while(pq.isEmpty() == false)
        {
            Meeting cur = pq.poll();
            if(cur.st >= end)
            {
                ans++;
                end = cur.ed;
            }
        }
        System.out.println(ans);
    }
}