数据结构与算法(八)贪心算法

定义

贪心算法又叫做贪婪算法,它在求解某个问题是,总是做出眼前最大利益。

特点

  • 局部最优解
  • 通过局部最优推出全局最优

习题

  1. 某天早上公司领导找你解决一个问题,明天公司有N个同等级的会议需要使用同一个会议室,现在给你这个N个会议的开始和结束时间,你怎么样安排才能使会议室最大利用?即安排最多场次的会议?
    会议时间:0点~9点 | 8点~10点 | 10点~12点 | 8点到~20点
    思考
    这里先给出解决方案:以结束时间按从小到大排序,就能得出最优解。
    首先为什么开始选择最小的9点而不是10点,由于一天只有24个小时,开始选择9点意味着后面还剩15个小时安排其他会议,而选择10点后面只剩14个小时安排会议,显然15个小时安排更多会议的可能性比14个小时安排更多会议的可能性要大,因此证明开始选择越小的结束时间越好。这里就是它的贪心策略。
    同理可得,当确认第一个之后,后面要选的只要选择开始时间>=前面会议的结束时间&&结束时间更小的那个,因为结束时间更小,给后面预留安排会议的时间越大嘛。以上。

代码

public class Meeting implements Comparable<Meeting> {

    public int number;
    public int startTime;
    public int endTime;

    public Meeting(int number, int startTime, int endTime) {
        this.number = number;
        this.startTime = startTime;
        this.endTime = endTime;
    }

    @Override
    public int compareTo(Meeting o) {
        if (endTime > o.endTime) return 1;
        return -1;
    }

    @Override
    public String toString() {
        return "Meeting{" +
                "number=" + number +
                ", startTime=" + startTime +
                ", endTime=" + endTime +
                '}';
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int next = scanner.nextInt();
        List<Meeting> meetings = new ArrayList<>();
        for (int i = 1; i <= next; i++) {
            int startTime = scanner.nextInt();
            int endTime = scanner.nextInt();
            meetings.add(new Meeting(i, startTime, endTime));
        }

        meetings.sort(null);
        System.out.println(meetings);
        System.out.println("===============");
        int curTime = 0;
        for (Meeting meeting : meetings) {
            if(meeting.startTime>=curTime){
                System.out.println(meeting);
                curTime = meeting.endTime;
            }
        }
    }
}
# 贪心 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×