<贪心>会议室宣讲&&哈弗曼树&&切金条&&LeetCode502IPO
原创<贪心>会议室宣讲&&哈弗曼树&&切金条&&LeetCode502IPO
原创
一、会议室宣讲
一些项目要占用一个会议室宣讲， 会议室不能同时容纳两个项目的宣讲。 给你每一个项目开始的时间和结束的时间(给你一个数组， 里面 是一个个具体的项目)， 你来安排宣讲的日程， 要求会议室进行 的宣讲的场次最多。 返回这个最多的宣讲场次。
这个也是一个贪心算法，优先考虑的是宣讲会结束时间早的那个。
二、哈弗曼树&&切金条
一块金条切成两半， 是需要花费和长度数值一样的铜板的。 比如长度为20的 金条， 不管切成长度多大的两半， 都要花费20个铜板。 一群人想整分整块金 条， 怎么分最省铜板？
例如,给定数组{10,20,30}， 代表一共三个人， 整块金条长度为10+20+30=60. 金条要分成10,20,30三个部分。 如果， 先把长度60的金条分成10和50， 花费60 再把长度50的金条分成20和30，花费50 一共花费110铜板。但是如果， 先把长度60的金条分成30和30， 花费60 再把长度30金条分成10和20， 花费30 一共花费90铜板。输入一个数组， 返回分割的最小代价。
//最小堆的比较器
public static class minHeapComparator implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
}
public static int lessMoney(int[] arr) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(new minHeapComparator());
for (int num : arr){
priorityQueue.add(num);
}
int sum = 0;
int cur = 0;
while (priorityQueue.size()>1){
cur = priorityQueue.poll() + priorityQueue.poll();
sum += cur;
priorityQueue.offer(cur);
}
return sum;
}采用一个最小堆，每次取出两个数，把和再添加到最小堆，以此往复。
实际上java默认的就是建立最小堆。
三、Leetcode502 IPO
输入： 参数1， 正数数组costs 参数2， 正数数组profits 参数3，正数k 参数4， 正数m costs[i]表示i号项目的花费 profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润) k表示你不能并行、 只能串行的最多做k个项目 m表示你初始的资金说明： 你每做完一个项目， 马上获得的收益， 可以支持你去做下一个 项目。
输出： 你最后获得的最大钱数
Input: k=2, W=0, Profits=[1,2,3], Capital=[0,1,1].
Output: 4
Explanation:
Since your initial capital is 0, you can only start the project indexed 0.
After finishing it you will obtain profit 1 and your capital becomes 1.
With capital 1, you can either start the project indexed 1 or the project indexed 2.
Since you can choose at most 2 projects, you need to finish the project
indexed 2 to get the maximum capital.
Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.采用一个最大堆和一个最小堆。由于两个数组都要放入堆里，那么怎么两个数组的相应元素的对应问题需要考虑，于是这里是新定义一种数据类型：psNode
public static class psNode{
int profits;
int costs;
public psNode(int profits, int cotes) {
this.profits = profits;
this.costs = cotes;
}
}
public static class ProfitsMaxHeap implements Comparator<psNode>{
@Override
public int compare(psNode o1, psNode o2) {
return o2.profits - o1.profits;
}
}
public static class CostsMinHeap implements Comparator<psNode>{
@Override
public int compare(psNode o1, psNode o2) {
return o1.costs - o2.costs;
}
}
public int findMaximizedCapital(int k, int W, int[] Profits, int[] Costs) {
psNode [] psNodes = new psNode[Profits.length];
for ( int i = 0;i < Profits.length;i++){
psNodes[i] = new psNode(Profits[i],Costs[i]);
}
PriorityQueue<psNode> profitsHeap = new PriorityQueue<>(new ProfitsMaxHeap());
PriorityQueue<psNode> costsHeap = new PriorityQueue<>(new CostsMinHeap());
for (psNode node : psNodes){
costsHeap.offer(node);
}
for (int i = 0; i < k; i++) {
while (!costsHeap.isEmpty() && costsHeap.peek().costs <= W){
profitsHeap.offer(costsHeap.poll());
}
if (profitsHeap.isEmpty()) return W;
W += profitsHeap.poll().profits;
}
return W;
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。