[백준] 1931번 회의실 배정

단계별로 풀어보기 그리디 알고리즘 2단계 문제

1931번: 회의실배정

파이썬의 좋은 점 중 하나가 (x, y)와 같은 순서쌍을 표현하고 싶을 때 클래스를 따로 만들지 않고 튜플을 이용하면 된다는 점인 것 같다.

자바는 튜플이 없어서 클래스를 하나 만들었다.

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        ArrayList li = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            li.add(new Tuple(in.nextInt(), in.nextInt()));
        }
        li.sort(new Comparator() {
            @Override
            public int compare(Tuple o1, Tuple o2) {
                if (o1.y - o2.y < 0)
                    return -1;
                else if (o1.y - o2.y > 0)
                    return 1;
                else
                    return o1.x - o2.x;
            }
        });
        ArrayList order = new ArrayList<>();
        int count = 0;
        order.add(li.get(0));
        count++;
        for (int i = 1; i < n; i++) {
            if(order.get(count - 1).y <= li.get(i).x) {
                count++;
                order.add(li.get(i));
            }
        }
        System.out.println(count);
    }
}
class Tuple {
    int x;
    int y;

    public Tuple(int x, int y) {
        this.x = x;
        this.y = y;
    }
}