[Softeer] 강의실 배정 (Java)

🔗 문제 링크: https://www.softeer.ai/practice/6291

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

 

📝 문제 요약

1️⃣ 강의 개수 N이 주어진다. N의 최댓값은 100만이다.
2️⃣ 각 강의마다 강의 시작 시간, 끝 시간이 주어진다. 각각의 값의 최댓값은 1억이고, 시작 시간은 항상 끝 시간보다 작다.
3️⃣ 하나의 강의실에서 배정할 수 있는 강의의 최대 개수를 구해야 한다.

 

🔍  해결 과정

한 개의 강의실에서 최대한 많은 강의를 배정 받기 위해서 각 강의들을 정렬하는 방식에 대해서 고민이 있었습니다.

 

강의 시작 시간을 우선으로 오름차순으로 정렬을 하는 방식과 강의 끝 시간을 우선으로 오름차순 정렬을 하는 방식에 대해 고민을 했었는데,

예시 그림을 그려보고 고민한 결과 강의를 최대한 많이 듣기 위해서는 끝시간이 빠른 강의를 우선으로 들어야 강의를 최대한 많이 들을 수 있을 것으로 결론을 지었습니다.

 

그래서 결국 끝시간을 기준으로 오름차순 정렬을 하고, 끝 시간이 같다면 시작 시간 기준 오름차순 하는 정렬 과정을 구현해서 강의 개수를 세어주는 방식으로 문제를 해결하였습니다.

 

---

✏️ 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int[][] times = new int[n][2];
        int answer = 0;
        StringTokenizer st;
        
        for (int i = 0; i < n; ++i) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            times[i][0] = start;
            times[i][1] = end;
        }

        Arrays.sort(times, (a, b) -> {
            if (a[1] == b[1]) {
                return a[0] - b[0];
            }

            return a[1] - b[1];
        });


        int curEnd = -1;
        for (int[] time : times) {
            int curStart = time[0];

            if (curEnd > curStart) {
                continue;
            }

            ++answer;
            curEnd = time[1];
        }
        
        bw.write(Integer.toString(answer));
        bw.flush(); 
    }
}