导师请吃火锅

题目描述:

入职后，导师会请你吃饭，你选择了火锅。火锅里会在不同时间下很多菜。不同食材要煮不同的时间，才能变得刚好合适。你希望吃到最多的刚好合适的菜，但你的手速不够快，用m代表手速，表示每次下手捞菜后至少要过m秒才能再捞(每次只能捞一个)。那么用最合理的策略，最多能吃到多少刚好合适的菜？

输入描述:

第一行两个整数n，m，其中n代表往锅里下的菜的个数，m代表手速。 (1<n, m<1000)

接下来有n行，每行有两个数x，y代表第x秒下的菜过y秒才能变得刚好合适。(1<x,y<1000)

输出描述:

输出一个整数代表用最合理的策略，最多能吃到刚好合适的菜的数量。

示例1

输入：

2	1
1	2
2	1

输出：

1

说明：

1. 总共有 2 个菜（n = 2），你的手速需要 1 秒的冷却时间（m = 1）。

2. 第一个菜在第 1 秒放入，需要 2 秒才能煮熟，所以这个菜在第 3 秒刚好煮熟。

3. 第二个菜在第 2 秒放入，需要 1 秒煮熟，所以在第 3 秒刚好煮熟。

4. 两个菜都在第 3 秒刚好煮熟，但你在第 3 秒只能捞一个，因为你捞完一个菜后要等 1 秒才能捞下一个菜。

5. 因此，你最多只能捞到其中一个刚好合适的菜，所以输出 1。

class Solution{
/** @param dishes a list of tuples consisting of two numbers, the first one is when the dish is added in the pot and the second is the time when you should eat it.
@param time   you have to wait for `time` second before you take the next dish
*/
public int eatHotPot(int[][] dishes, int time) {
//      当前时刻吃或不吃？
//      如果吃，接下来 +time 冷却时间
//      如果不吃，下一时刻可以继续选择
        int ans = 0;
        //菜的个数
        int sum = dishes.length;
        //计算下有菜吃的时刻
        int[] eat = new int[sum];
        for (int i = 0; i < sum; i++) {
            eat[i] = dishes[i][0] + dishes[i][1];
        }
        eat = Arrays.stream(eat).sorted().distinct().toArray();
        int[][] memo = new int[eat.length + 1][2];
        Arrays.fill(memo, new int[]{-1, -1});

        return dfs_eatHotpot(0, 0, eat, time, memo);
    }

    private int dfs_eatHotpot(int i, int t, int[] eat, int time, int[][] memo) {
        if (i == eat.length) {
            return 0;
        }
        int res = 0;
        if (eat[i] < t) {//当前时刻不能吃
            res = memo[i][0] == -1 ? dfs_eatHotpot(i + 1, t, eat, time, memo) : memo[i][0];
            return res;
        }
        res = memo[i][1] == -1 ? Math.max(dfs_eatHotpot(i + 1, t, eat, time, memo),
                dfs_eatHotpot(i + 1, eat[i] + time, eat, time, memo) + 1) : memo[i][1];
        return res;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] dishes = new int[][]{{2, 1}, {1, 2}, {1, 3}, {4, 2}, {3, 3}};
        int time = 4;
        System.out.println("You can eat " + sol.eatHotPot(dishes, time) + " dishes at most!");
    }
}