贪心算法 -判断能否满足时间填充

本文主要是介绍贪心算法 -判断能否满足时间填充，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

import java.util.Arrays;

/**
 * @author 
 * Created on 2021-05-01
 */
public class GreedyUtils {

    /**
     * 贪心算法工具类
     * 实现：一个时间轴是否被其他片段时间充满
     * 例如：
     * A：2-20
     * B：中有多个片段 2-7，7-15，15-21 是否能够充满A
     */
    public static boolean videoStitching(long[][] clips, long t) {
        if (t == 0) {
            return false;
        }
        // 按起点升序排列，起点相同的降序排列
        Arrays.sort(clips, (a, b) -> {
            if (a[0] == b[0]) {
                if (b[1] > a[1]) {
                    return 1;
                } else if (b[1] == a[1]) {
                    return 0;
                } else {
                    return -1;
                }
                // return (b[1] - a[1]);
            }

            if (a[0] > b[0]) {
                return 1;
            } else if (a[0] == b[0]) {
                return 0;
            } else {
                return -1;
            }
            //return (a[0] - b[0]);
        });
        // 记录选择的时间段个数
        //int res = 0;

        long curEnd = 0, nextEnd = 0;
        int i = 0, n = clips.length;
        while (i < n && clips[i][0] <= curEnd) {
            // 在第 res 个时间点的区间内贪心选择下一个时间范围
            while (i < n && clips[i][0] <= curEnd) {
                nextEnd = Math.max(nextEnd, clips[i][1]);
                i++;
            }
            // 找到下一个时间点，更新 curEnd
            // res++;
            curEnd = nextEnd;
            if (curEnd >= t) {
                // 已经可以拼出区间 [0, T]
                return true;
            }
        }
        // 无法连续拼出区间 [0, T]
        return false;
    }
}

 /**
     * 判断能否满足时间填充
     * 备注：通过包的开始时间到结束时间形成一个时间轴，然后计划列表中开始时间到结束时间是否充满整个时间轴
     */
    public boolean isToUp(List<PlanDo> planDoList, PackDo packDo) {
        if (CollectionUtils.isEmpty(planDoList) || packDo == null) {
            return false;
        }
        long packEndTime = packDo.getPackEndTime();
        long packStartTime = packDo.getPackStartTime();
        long[][] r = new long[planDoList.size()][2];
        //1.同等去做坐标式平移（同时都减包的开始时间）
        for (int i = 0; i < planDoList.size(); i++) {
            r[i][0] = planDoList.get(i).getDeliveryStartTime() - packStartTime;
            r[i][1] = planDoList.get(i).getDeliveryEndTime() - packStartTime;
        }
        //2.贪心算法计算是否填满整个时间轴
        return GreedyUtils.videoStitching(r, (packEndTime - packStartTime));
    }

这篇关于贪心算法 -判断能否满足时间填充的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！