算法-贪心-会议安排问题

2022-4-18 diaba 算法 

package com.jiucaiyuan.net.question;

import java.util.Arrays;
import java.util.Comparator;

/**
 * <pre>
 * 贪心算法
 *  在某一个标准下，优先考虑最满足标准的样本，最后考虑最不满足标准的样本，
 *  最终得到一个答案的算法，叫做贪心算法
 *  也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解
 *
 * 实例题：会议问题
 * 问题内容：一些项目要占用会议室宣讲，会议室不能同时容纳两个项目同时宣讲。
 *  给你每个项目的开始时间和结束时间（给你一个数组，里面是一个个具体的项目），
 *  你来安排宣讲的日程，要求会议室进行宣讲的场次最多。
 *  返回这个最多的宣讲场次。
 *
 *  贪心：会议结束的时间早的先安排，安排一个后，把不能安排的剔除掉，这个会议结束后，再找会议结束早的，一次类推
 * </pre>
 *
 * @Author jiucaiyuan  2022/4/18 23:36
 * @mail services@jiucaiyuan.net
 */

public class BestArrangeMeeting {
    public static class Program{
        public int start;
        public int end;
        public Program(int start,int end){
            this.start = start;
            this.end = end;
        }
    }
    public static class ProgramComparator implements Comparator<Program>{

        @Override
        public int compare(Program o1, Program o2) {
            return o1.end - o2.end;
        }
    }

    /**
     *
     * @param programs 一堆项目
     * @param timePoint 会议室可用的开始时间点
     * @return
     */
    public static int bestArrange(Program[] programs,int timePoint){
        Arrays.sort(programs,new ProgramComparator());
        int result = 0;
        for(int i=0;i<programs.length;i++){
            if(timePoint <= programs[i].start){
                result++;
                timePoint = programs[i].end;
            }
        }
        return result;
    }

    public static void main(String[] args) {

    }
}

« 算法-贪心-做项目获得最大收益 | 算法-贪心-成本最小切金条»

发表评论：

Powered by emlog 京ICP备15045175号-1 Copyright © 2022