문제

풀이

package Inflearn.greedy.meetingRoom;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<MeetingTime> meetingTimeList = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int startTime = sc.nextInt();
            int endTime = sc.nextInt();
            meetingTimeList.add(new MeetingTime(startTime, endTime));
        }

        System.out.println(new Main().solution(meetingTimeList));

    }

    public int solution(List<MeetingTime> meetingTimeList) {

        int answer = 0;
        int lastMeetingTime = 0;
        Collections.sort(meetingTimeList);

        for (MeetingTime meetingTime : meetingTimeList) {
            if (lastMeetingTime == 0) {
                answer++;
                lastMeetingTime = meetingTime.getEndTime();
            }

            if (meetingTime.getStartTime() >= lastMeetingTime) {
                answer++;
                lastMeetingTime = meetingTime.getEndTime();
            }

        }

        return answer;
    }
}

class MeetingTime implements Comparable<MeetingTime> {

    private int startTime;
    private int endTime;

    public int getStartTime() {
        return startTime;
    }

    public int getEndTime() {
        return endTime;
    }


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

    public int compareTo(MeetingTime meetingTime) {

        if (this.endTime == meetingTime.endTime) {
            return this.startTime - meetingTime.startTime;
        }

        return this.endTime - meetingTime.endTime;
    }

}

그리디 알고리즘을 처음 접하면서 아직 문제를 어떻게 해결해야 할지 감이 오지 않는다.
당장 최선의 선택을 통해 문제를 해결을 해야한다는 풀이법이 추상적인 느낌이였다.

이 문제에서는 회의시간의 끝나는 시간을 기준으로 정렬을 하면 쉽게 풀이되었다.
회의가 끝나는 시간을 내림차순으로 정렬하여 고르는게 당장 최선의 선택이였다.

조심해야하는 부분은, (1 3) (2 3) (3 3) 처럼 회의가 끝나는 시간이 동일한 case인데, 이 경우에는 comapreTo에서 조건문을 통해 startTime을 기준으로 정렬하면 된다