백준 7983 (내일 할거야) - java

https://www.acmicpc.net/problem/7983

7983번: 내일 할거야

유형 : 그리디

해결하는 방법은 조금만 생각해보면 간단하다. 핵심은 1일을 기준으로 최대 쉴수 있는 날을 찾는 것이다 !

가장 기한이 긴 것부터 정렬하여 걸리는 시간만큼 할당한다.

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

public class Main {
    static int n = 0;
    static int m = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(st.nextToken());

        int[][] homework = new int[n][2];

        for(int i=0;i<n;i++)
        {
            st = new StringTokenizer(br.readLine(), " ");
            int t = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            homework[i][0] = t;
            homework[i][1] = d;
        }

        Arrays.sort(homework,(x,y) ->{
            if(x[1] == y[1])
                return y[0] - x[0];

            return y[1] - x[1];
        });

        int ld = homework[0][1];
        int sd = homework[0][1] - homework[0][0];

        for(int i=1;i<n;i++)
        {
            if(sd > homework[i][1])
            {
                sd = homework[i][1]; // 만약 데드라인이 더 앞 날이라면 당겨준다.
            }

            sd = sd - homework[i][0]; // 일정을 배치

        }

        System.out.println(sd);

        br.close();
    }
}

시간 복잡도를 줄이고 싶다면 우선순위 큐를 사용하면 된다.