小明上学，老师布置了 n 个作业，每个作业恰好需要一天做完，每个作业都有最后提交时间ti及其逾期的扣分ki。已知作业n = 3，每个作业的最后提交时间t = [1,3,1]，作业逾期扣分k = [6,2,3]。以输入n = 0时作为结束，请给出小明做作业的顺序，以便扣最少的分数。使用贪心算法求解，并给出java代码

题目描述

小明上学，老师布置了 n 个作业，每个作业恰好需要一天做完，每个作业都有最后提交时间 $t_i$ 及其逾期的扣分 $k_i$。已知作业 $n=3$，每个作业的最后提交时间 $t=[1,3,1]$，作业逾期扣分 $k=[6,2,3]$。以输入 $n=0$ 时作为结束，请给出小明做作业的顺序，以便扣最少的分数。

解题思路

贪心算法，按照最后提交时间从小到大排序，每次选择最早的未完成的作业完成，若已经超时，则直接放弃此作业。

Java代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static class Homework implements Comparable<Homework> {
        int t; // 最后提交时间
        int k; // 逾期扣分

        public Homework(int t, int k) {
            this.t = t;
            this.k = k;
        }

        @Override
        public int compareTo(Homework o) {
            return Integer.compare(this.t, o.t);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            int n = sc.nextInt();
            if (n == 0) {
                break;
            }
            Homework[] hws = new Homework[n];
            for (int i = 0; i < n; i++) {
                int t = sc.nextInt();
                int k = sc.nextInt();
                hws[i] = new Homework(t, k);
            }
            Arrays.sort(hws);
            int curTime = 0, totalK = 0; // 当前时间、总扣分
            for (int i = 0; i < n; i++) {
                if (curTime + 1 <= hws[i].t) { // 没有逾期
                    curTime++;
                    totalK += hws[i].k;
                }
            }
            System.out.println(totalK);
        }
        sc.close();
    }
}