백준 1931번 <회의실 배정>

백준 알고리즘 1931번

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

1931번: 회의실 배정

---

1931번

첫째 줄에 회의의 수가 들어오고 둘째 줄부터 각 회의에 대한 정보가 들어온다. (시작 시간과 끝나는 시간)

 

최대 사용할 수 있는 회의의 개수를 출력하면 된다.

---

문제 해결

그리디 알고리즘으로 해결할 수 있다.

회의 종료 시간을 기준으로 정렬하여 선택할 수 있는 회의를 선택하면 된다.

 

종료시간이 가장 빠른 회의는 무조건 선택한다. 

why? 

종료시간이 가장 빠른 회의를 A, 그 다음으로 빠른 회의를 B라고 하자.

두 개의 회의가 다음 회의로 고를 수 있는 회의는 아래의 3가지 경우가 있다.

1. A가 진행 중일 때 들어오는 회의
2. B가 끝나는 시간 이후에 들어오는 회의 
3. A가 끝나는 시간과 B가 끝나는 시간 사이에 들어오는 회의

→ 1번은 A와 B 둘 다 선택 불가능.

→ 2번은 A와 B 둘 다 선택 가능.

→ 3번은 A만 선택 가능.

 

따라서 종료시간이 가장 빠른 회의를 선택하는 것이 최선이다.

---

코드

def main():
    n = int(input())
    data = []
    for i in range(n):

        j, k = map(int, input().split())
        data.append((k, j))
    sort_Data = sorted(data)

    result = 1
    index = 0
    for i in range(n):
        if i == 0:
            continue
        else:
            if sort_Data[index][0] <= sort_Data[i][1]:
                result += 1;
                index = i
    print(result)
if __name__ == '__main__':
    main()

 

JAVA (2022.08.03)

package bj1931;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

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());
		Tuple[] times = new Tuple[n];
		for (int i = 0; i < n; i++) {
			String[] inArr = br.readLine().split(" ");
			int s = Integer.parseInt(inArr[0]);
			int e = Integer.parseInt(inArr[1]);

			times[i] = new Tuple(s, e);
		}
		Arrays.sort(times);
		int cnt = 1;
		int end = times[0].end;
		for (int k = 1; k < n; k++) {
			if (times[k].start >= end) {
				end = times[k].end;
				cnt++;
			}
		}
		System.out.println(cnt);
	}

}

class Tuple implements Comparable<Tuple> {
	int start, end;

	public Tuple(int s, int e) {
		start = s;
		end = e;
	}

	@Override
	public int compareTo(Tuple o) {
		if (this.end > o.end) {
			return 1;
		} else if (this.end == o.end) {
			if (this.start > o.start) {
				return 1;
			} else if (this.start == o.start) {
				return 0;
			} else {
				return -1;
			}
		} else {
			return -1;
		}
	}
}

---

결과

JAVA

---

가장 빨리 끝나는 회의를 고르지 않고 그 다음 회의도 고를 수 있다고 생각하여 for문을 돌렸을 때,  시간초과가 났다.

다시 생각해보니 가장 빨리 끝나는 회의는 꼭 골라야하기 때문에 for문을 생략하였고 통과할 수 있었다.