广告收益有时间区间和奖励金额，求最佳组合。
/*
* 简单的广告投放排期程序
*
* 给出一组数据，每个元素包括投放开始时间、结束时间、广告主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)
