广告收益最大化

广告收益有时间区间和奖励金额，求最佳组合。

/*
 * 简单的广告投放排期程序
 * 
 * 给出一组数据，每个元素包括投放开始时间、结束时间、广告主id以及出价金额(单位为元，且为一小时的出价)。
 * 
 * 其中开始结束都按照int设计。
 * 
 * 后一个元素可以打破前一个元素的排期，比如A在8点到10点出10块一小时，如果B在9点到10点出20块一小时，则A的投放排期会被改为8到9点让A投，
 * 9到10点让B投。
 * 
 * 请设计一个程序，使得整体的广告排期可以使收入最大化。
 */
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Comparator;

class Plan {
    public int start_time;
    public int end_time;
    public int id;
    public int price;

    public Plan(int start_time, int end_time, int id, int price) {
        this.start_time = start_time;
        this.end_time = end_time;
        this.id = id;
        this.price = price;
    }
}

class Test {
    public static void orderPlan(PriorityQueue<Plan> pq) {
        int timestamp_now = pq.element().start_time;
        while (!pq.isEmpty()) {
            // select the highest price that start_time <= timestamp_now and end_time >
            ArrayList<Plan> arr = new ArrayList<>();
            Plan topPlan = new Plan(timestamp_now, timestamp_now, -1, -1);
            while (!pq.isEmpty() && pq.element().start_time <= timestamp_now) {
                if(pq.element().end_time > timestamp_now){
                    arr.add(pq.element());
                    if (topPlan.price < pq.element().price) {
                        topPlan = pq.element();
                    }
                }
                pq.remove();
            }

            // no intersection
            if (topPlan.id == -1) {
                // choose next plan
                if (!pq.isEmpty()) {
                    System.out.printf("skip %d-%d\n", timestamp_now, pq.element().start_time);
                    timestamp_now = pq.element().start_time;
                } else {
                    // final
                    return;
                }
            } else {
                // has intersection, choose the next plan's start_time as next timestamp_now
                // if next plan(not equal) is later than current end_time
                if (!pq.isEmpty() && pq.element().start_time > topPlan.end_time) {
                    System.out.printf("[ID:%d]%d-%d\n", topPlan.id, timestamp_now, topPlan.end_time);
                    timestamp_now = topPlan.end_time;
                } else if (!pq.isEmpty() && pq.element().start_time < topPlan.end_time) {
                    while (!pq.isEmpty() && pq.element().start_time < topPlan.end_time) {
                        if (pq.element().price > topPlan.price) {
                            System.out.printf("[ID:%d]%d-%d\n", topPlan.id, timestamp_now, pq.element().start_time);
                            timestamp_now = pq.element().start_time;
                            break;
                        }
                        arr.add(pq.element());
                        pq.remove();
                    }
                    if (pq.isEmpty()) {
                        System.out.printf("[ID:%d]%d-%d\n", topPlan.id, timestamp_now, topPlan.end_time);
                        timestamp_now = topPlan.end_time;
                    } else {
                        if (pq.element().start_time < topPlan.end_time) {
                            System.out.printf("[ID:%d]%d-%d\n", topPlan.id, timestamp_now, pq.element().start_time);
                            timestamp_now = pq.element().start_time;
                        } else {
                            System.out.printf("[ID:%d]%d-%d\n", topPlan.id, timestamp_now, topPlan.end_time);
                            timestamp_now = topPlan.end_time;
                        }
                    }
                } else if (pq.isEmpty()) {
                    System.out.printf("[ID:%d]%d-%d\n", topPlan.id, timestamp_now, topPlan.end_time);
                    timestamp_now = topPlan.end_time;
                }
            }

            for (int i = 0; i < arr.size(); i++) {
                if (arr.get(i).end_time > timestamp_now) {
                    pq.add(arr.get(i));
                }
            }
        }
    }

    public static void main(String[] args) {
        PriorityQueue<Plan> pq = new PriorityQueue<>(1, new Comparator<Plan>() {
            @Override
            public int compare(Plan a, Plan b) {
                if (a.start_time == b.start_time) {
                    // money next
                    return a.price - b.price;
                } else {
                    return a.start_time - b.start_time;
                }
            }
        });

        // [0-10]
        pq.add(new Plan(0, 10, 1, 2));
        pq.add(new Plan(7, 9, 2, 10));
        pq.add(new Plan(8, 10, 3, 11));
        pq.add(new Plan(18, 20, 4, 11));

        orderPlan(pq);
    }
}

• 我的解题思路：

通过优先队列，按照start time小的优先，如果start_time相同则price高的优先。

有一个timestamp指针，该时间点会有一个最优的广告A，但是这个广告的end time不一定是当前最优的end time，因为可能有price更高，但是start time比当前选中的广告A更早开始的广告B作为下一片段的开始。此时需要按照时间顺序查找start time> A的end time 且 price > 广告A price的下一个潜在广告B。

如果A和B之间没有交集，那就设置timestamp为A的end time，因为可能有其他广告可以衔接A和B之间的空白。

如果A和B有交集，那就设置timestamp为B的start time。

• 期间end time < timestamp的广告需要剔除。可能产生交集成为潜在A或者可能成为下一条广告B的需要回填优先队列。

• 时间复杂度：O(nlog2n)