[백준 - Java] 1931번 : 회의실 배정

문제

www.acmicpc.net/problem/1931

1931번: 회의실 배정

---

처음엔 막 시작시간이랑 끝 시간이랑 비교하고 이중 for문 쓰면서 삽질했는데 시간 초과남~~!

정렬을 써서 for문은 최대한 한번으로 끝내도록 설계해야 함

 

끝나는 시간을 기준으로 오름차순 정렬, 끝나는 시간이 같다면 시작 시간 기준 오름차순으로 정렬을 해놓는다.

 

끝나는 시간이 제일 빠른 회의부터 마지막 회의까지 돌면서

 

현재 회의의 끝나는 시간과 같거나 더 늦은 시간에 시작하는 회의라면 회의실을 사용할 수 있다.

 

이런 식으로 마지막까지 확인하면 사용할 수 있는 최대의 회의수를 구할 수 있다.

전체 코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

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

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

    @Override
    public int compareTo(Time t) {
        if (this.end > t.end) { // 끝나는 시간 기준 오름차순 정렬 
            return 1;
        } else if (this.end == t.end) {
            if(this.start > t.start) { // 끝나는 시간 같다면 시작 시간 기준 오름차순 
            	return 1;
            } else {
            	return -1;
            }
        } else {
        	return -1;
        }
    }
}

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();

		ArrayList<Time> timeList = new ArrayList<>();
		for(int i = 0; i < N; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();

			timeList.add(new Time(a, b));
		}
		
		Collections.sort(timeList);
		
		int ans = 1;
		int endTime = timeList.get(0).end;
		for(int i = 1; i < timeList.size(); i++) {
			if(timeList.get(i).start >= endTime) {
				endTime = timeList.get(i).end;
				ans++;
			}
		}
		
		System.out.println(ans);
	}
}

 

GITHUB

github.com/KwonMinha/BOJ/blob/master/BOJ%231931/src/Main.java

KwonMinha/BOJ