資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++ 中作業排程中的最大利潤
假設我們有 n 個不同的任務，每個任務安排在從 startTime[i] 到 endTime[i] 的時間段內完成，對於該任務，我們還可以獲得 profit[i] 的利潤。我們已知 startTime、endTime 和 profit 列表，我們必須找到我們可以獲得的最大利潤，這樣子集中就不會有兩個任務的時間範圍重疊。如果我們選擇一個在時間 X 結束的任務，我們將能夠開始另一個在時間 X 開始的任務。
因此，如果輸入類似於 startTime = [1,2,3,3]，endTime = [3,4,5,6]，profit = [500,100,400,700]
則輸出將為 1200
為了解決這個問題，我們將遵循以下步驟：
- 定義一個包含起始時間、結束時間和成本值的資料結構。
建立一個 Data 型別的陣列 j。
n := s 的大小
初始化 i := 0，當 i < n 時，更新（i 增加 1），執行：
建立一個 Data 型別的臨時變數 temp(s[i], e[i], p[i])
將 temp 插入到 j 的末尾。
根據結束時間對陣列 j 進行排序。
定義一個大小為 n 的陣列 dp。
dp[0] := j[0].cost
初始化 i := 1，當 i < n 時，更新（i 增加 1），執行：
temp := 0, low := 0, high := i - 1
當 low < high 時，執行：
mid := low + (high - low + 1) / 2
如果 j[mid].end <= j[i].start，則：
low := mid
否則
high := mid - 1
dp[i] := j[i].cost
如果 j[low].end <= j[i].start，則：
dp[i] := dp[i] + dp[low]
dp[i] := dp[i] 和 dp[i - 1] 的最大值
返回 dp[n - 1]
讓我們看看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
struct Data{
int s,e,c;
Data(int x, int y, int z){
s= x;
e= y;
c = z;
}
};
bool cmp(Data a, Data b){
return a.e<b.e;
}
class Solution {
public:
int jobScheduling(vector<int>& s, vector<int>& e, vector<int>& p){
vector<Data> j;
int n = s.size();
for (int i = 0; i < n; i++) {
Data temp(s[i], e[i], p[i]);
j.push_back(temp);
}
sort(j.begin(), j.end(), cmp);
vector<int> dp(n);
dp[0] = j[0].c;
for (int i = 1; i < n; i++) {
int temp = 0;
int low = 0;
int high = i - 1;
while (low < high) {
int mid = low + (high - low + 1) / 2;
if (j[mid].e <= j[i].s)
low = mid;
else
high = mid - 1;
}
dp[i] = j[i].c;
if (j[low].e <= j[i].s)
dp[i] += dp[low];
dp[i] = max(dp[i], dp[i - 1]);
}
return dp[n - 1];
}
};
main(){
Solution ob;
vector<int> startTime = {1,2,3,3}, endTime = {3,4,5,6}, profit =
{500,100,400,700};
cout << (ob.jobScheduling(startTime, endTime, profit));
}輸入
{1,2,3,3}, {3,4,5,6}, {500,100,400,700}輸出
1200
959 次瀏覽
