[소프티어] 강의실 배정(JAVA)

문제

https://softeer.ai/practice/6291

---

풀이(25분)

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

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());

        Lecture[] lectures = new Lecture[n];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int startTime = Integer.parseInt(st.nextToken());
            int endTime = Integer.parseInt(st.nextToken());
            lectures[i] = new Lecture(startTime, endTime);
        }

        // 종료 시간이 빠른 순으로 정렬, 같으면 시작 시간이 빠른 순으로 정렬
        Arrays.sort(lectures);

        int lectureCount = 0;
        int lastEndTime = 0;

        for (Lecture lecture : lectures) {
            if (lecture.startTime >= lastEndTime) { // 현재 강의의 시작 시간이 이전 강의 종료 시간 이후라면
                lectureCount++;
                lastEndTime = lecture.endTime;
            }
        }

        System.out.println(lectureCount);
    }

    static class Lecture implements Comparable<Lecture> {
        int startTime;
        int endTime;

        public Lecture(int startTime, int endTime) {
            this.startTime = startTime;
            this.endTime = endTime;
        }

        @Override
        public int compareTo(Lecture other) {
            if (this.endTime != other.endTime) {
                return this.endTime - other.endTime; // 종료 시간 기준 오름차순 정렬
            }
            return this.startTime - other.startTime; // 종료 시간이 같으면 시작 시간 기준 오름차순 정렬
        }
    }
}

---

문제 풀이 전략

 

dp풀이를 고려했지만 최대 시간이 10억인 관계로 포기했다.

 

단순하게 그리디로 종료 시간이 가장 빠른 것부터 탐색해 나가면 되는 문제였다.