백준 1931 그리디 알고리즘

출처: https://www.acmicpc.net/problem/1931

소스코드

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Baek1931 {
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        List<int[]> meetings = new ArrayList<int[]>();
        n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            String [] temp = br.readLine().split(" ");
            int start = Integer.parseInt(temp[0]);
            int end = Integer.parseInt(temp[1]);
            meetings.add(new int[]{start, end});
        }
        Collections.sort(meetings,(a,b)->{
            if(a[1]==b[1])
                return a[0]-b[0];
            return a[1]-b[1];
        });
        int result = 0;
        int prevEnd = 0;
        for (int i = 0; i < n; i++) {
            if(prevEnd<=meetings.get(i)[0]){
                result++;
                prevEnd = meetings.get(i)[1];
            }
        }
        System.out.println(result);
    }
}

느낀점 : 처음에 문제를 풀이할 때, 정렬 기준을 시작시간으로 오름차순 시작시간이 같을 때, 끝나는 시간을 기준으로 오름차순 정렬되도록 하여 문제를 풀이하였고, 차례로 완전탐색을 진행할 수 밖에 없었다. 하지만 시간초과가 발생했고, 정렬기준을 끝나는 시간으로 오름차순, 끝나는 시간이 같을 때 오름차순으로 정렬하였고, 완전탐색을 고려할 부분이 필요가 없어졌다.