[Softeer] 강의실 배정 (JAVA)

https://softeer.ai/practice/info.do?idx=1&eid=392 

Softeer

---

문제

김교수는 강의실 1개에 최대한 많은 강의를 배정하려고 한다. 배정된 강의는 서로 겹치지 않아야 하며 수업시간의 길이와 상관없이 최대한 강의를 많이 배정하라. 단, 두 강의의 시작시간과 종료시간은 겹쳐도 된다. 

제약조건

1 ≤ N ≤ 106 인 정수
1 ≤ Si ＜ Fi ≤ 109

입력형식

첫 번째 줄에 강의 개수 N이 주어진다. i + 1 (1 ≤ i ≤ N)번째 줄에는 i번째 강의의 시작 시간 Si와 종료 시간 Fi가 주어진다.

출력형식

첫 번째 줄에 최대 강의 수를 출력하라.

입력예제1

3
1 3
2 4
3 5

출력예제1

2

---

※ JAVA코드 (강의실 배정)

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


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

public class Main {

    // 시간 범위를 담을 클래스
    static class Time {
        int s, f;
        Time(int s, int f) {
            this.s = s;
            this.f = f;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        int result = 1;
        int N = Integer.parseInt(br.readLine());
        int S, F;
        Time[] cls = new Time[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            S = Integer.parseInt(st.nextToken());
            F = Integer.parseInt(st.nextToken());
            cls[i] = new Time(S, F);
        }

        Arrays.sort(cls, (c1, c2) -> {
            return Integer.compare(c1.f, c2.f);
        });
        int val = cls[0].f;

        for (int i = 1; i < N; i++) {

            if(val <= cls[i].s) {
                val = cls[i].f;
                result++;
            }
        }

        System.out.println(result);
    }
}

---

※ 생각정리 (강의실 배정)

 

강의실 배정문제는 쉽게말해 사간의 범위를 정렬하는 문제였으며 시작시간, 종료시간을 담기위한 클래스를 만들어 사용하였다.

해당 객체의 원소중 시작시간 혹은 종료시간 한가지로 정렬이 필요하므로, 람다식을 통해 객체 정렬을 하였다.

정렬후 이전 강의 시간의 종료시간보다 다음 강의시간의 시작시간이 크면 해당 시간을 제외하고 반복문을 진행했다.

 

- 새벽코딩 -