문제 링크

풀이

대표적인 그리디 알고리즘을 사용하여 풀 수 있는 문제이다.
강의 종료시간을 기준으로 오름차순으로 정렬 후, 현재 시간(이전에 선택한 강의 종료시간)보다 강의 시작시잔이 작으면 선택하지 않고 같거나 클 경우 선택하면 된다.

코드

package Softeer;

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

public class Main {
    static int N;
    static List<Lecture> lectures;
    static int result = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        lectures = new ArrayList<>();
        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int f = Integer.parseInt(st.nextToken());
            lectures.add(new Lecture(s, f));
        }

        lectures.sort((l1, l2) -> Integer.compare(l1.f, l2.f));

        int currTime = 0;
        for (Lecture l : lectures) {
            if (currTime > l.s) {
                continue;
            }
            currTime = l.f;
            result++;
        }
        System.out.println(result);
    }

    public static class Lecture {
        int s;
        int f;

        public Lecture(int s, int f) {
            this.s = s;
            this.f = f;
        }
    }
}