Leetcode每日一题 —— 3633. 最早完成陆地和水上游乐设施的时间 I

3633. 最早完成陆地和水上游乐设施的时间 I - 力扣（LeetCode）

3633. 最早完成陆地和水上游乐设施的时间 I - 给你两种类别的游乐园项目：陆地游乐设施 和 水上游乐设施。 * 陆地游乐设施 * landStartTime[i] – 第 i 个陆地游乐设施最早可以开始的时间。 * landDuration[i] – 第 i 个陆地游乐设施持续的时间。 * 水上游乐设施 * waterStartTime[j] – 第 j 个水上游乐设施最早可以开始的时间。 * waterDuration[j] – 第 j...

思路
记录每个时刻 早于此刻开始的水上设施的最短持续时间 shortestDuration 和 晚于此刻开始的的水上设施的最早结束时间 earliestFinishTime 还有 所有水上设施中最早完成的时间 firstFinishTime。
然后遍历 陆地设施，统计最短的( endTime = landStartTime[i] + landDuration[i])

1. 陆地设施晚于firstFinishTime的，计当前陆地设施的完成时间。否则取以下三者最小的。
2. firstFinishTime + landDuration[i]
3. endTime + shortestDuration[endTime]
4. earliestFinishTime[endTime]

代码

class Solution {
    private static class Rides {
        int startTime;
        int duration;
        int endTime;
        public Rides(int startTime, int duration) {
            this.startTime = startTime;
            this.duration = duration;
            this.endTime = startTime + duration;
        }
    }
    public int earliestFinishTime(int[] landStartTime, int[] landDuration, int[] waterStartTime, int[] waterDuration) {
        int n = landStartTime.length, m = waterStartTime.length;
        Rides[] water = new Rides[m];
        int firstFinishTime = Integer.MAX_VALUE;
        int maxLand = 0, maxWater = 0;
        for (int i = 0; i < n; i++) {
            maxLand = Math.max(maxLand, landStartTime[i] + landDuration[i]);
        }
        for (int i = 0; i < m; i++) {
            water[i] = new Rides(waterStartTime[i], waterDuration[i]);
            firstFinishTime = Math.min(firstFinishTime, water[i].endTime);
            maxWater = Math.max(maxWater, water[i].endTime);
        }
        int max = maxLand + maxWater;
        Arrays.sort(water, (a, b) -> {
            if (a.startTime != b.startTime) {
                return Integer.compare(a.startTime, b.startTime);
            } else {
                return Integer.compare(a.duration, b.duration);
            }
        });
        int idx = 0;
        int minDuration = Integer.MAX_VALUE >> 1;
        int[] shortestDuration = new int[max + 1];
        for (int i = 0; i <= max; i++) {
            while (idx < m && water[idx].startTime < i) {
                minDuration = Math.min(minDuration, water[idx].duration);
                idx++;
            }
            shortestDuration[i] = minDuration;
        }
        idx = m - 1;
        int lastTime = Integer.MAX_VALUE >> 1;
        int[] earliestFinishTime = new int[max + 1];
        for (int i = max; i >= 0; i--) {
            while (idx >= 0 && water[idx].startTime >= i) {
                lastTime = Math.min(lastTime, water[idx].endTime);
                idx--;
            }
            earliestFinishTime[i] = lastTime;
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (landStartTime[i] > firstFinishTime) {
                ans = Math.min(ans, landStartTime[i] + landDuration[i]);
            } else {
                ans = Math.min(ans, firstFinishTime + landDuration[i]);
                int endTime = landStartTime[i] + landDuration[i];
                ans = Math.min(ans, endTime + shortestDuration[endTime]);
                ans = Math.min(ans, earliestFinishTime[endTime]);
            }
        }

        return ans;
    }
}

3 个帖子 - 3 位参与者

阅读完整话题