# 貪婪
## 工作排程1
:::success
最多有幾個工作可以執行
:::
### 題目說明
有$n$個工作可以執行，給定每個工作的開始時間與結束時間，時間從$0$開始，開始與結束時間都是整數，只有一台機器可以執行，每次只能執行一個工作，且工作一旦開始就必須做完，機器執行中不能跳到另一個工作，可以一結束就馬上接著執行另一個工作，機器更換工作很快，可以不考慮切換所需時間，請計算執行完後最多有幾個工作被完成？
### 輸入說明
每次輸入數字$n$，$n$表示需要執行的工作個數，輸入$n$小於$100$，之後有$n$行分別是每一行兩個整數$s$與$e$，$s$表示工作的開始時間與$e$表示工作的結束時間，且$s$永遠小於$e$。
### 輸出說明
輸出一個數字，表示結束時最多有幾個工作被完成。
### 輸入輸出範例
輸入範例
5
1 10
2 4
3 6
2 5
4 9
輸出範例
2
```cpp=
#include <iostream>
#include <algorithm> // for sort()
using namespace std;
//定義一個工作的資料型別
/*
struct JOB{
int start; //工作開始時間
int end; //工作結束時間
};
*/
typedef struct _job{
int start;
int end;
}JOB;
const int MAXN = 100+5; //最大的工作數量
JOB jobs[MAXN]; //儲存所有輸入工作的陣列
bool cmp(JOB p, JOB q){
if(p.end==q.end) return(p.start<q.start);
else return (p.end<q.end);
}
//顯示陣列內容;驗證輸入資料
void showArray(int n)
{
for(int i=0;i<n;++i){
cout<<jobs[i].start<<" "<<jobs[i].end<<"\n";
}
}
int main()
{
//工作輸入: n筆工作
int n;
//不斷輸入n筆工作直到使用者按下ctrl+Z
while(cin>>n){
//將n筆工作讀入並存入陣列中
for(int i=0;i<n;++i){
cin>>jobs[i].start>>jobs[i].end;
}
sort(jobs, jobs+n, cmp);
//showArray(n);
//模擬工作運算
int res=0; //紀錄已經完成的工作數量
int curTime = -1; //代表目前工作時間
for(int i=0; i<n; i++){
//目前機器可以執行第i個工作
if(curTime<=jobs[i].start){
//設定工作時間至第i個工作結束的時間
curTime=jobs[i].end;
res++; //可執行工作+1
}
}cout<<res<<"\n";
}
return 0;
}
```
## 工作排程2
:::success
最多有幾台機器一起運作
:::
### 題目說明
有$n$個工作可以執行，給定每個工作的開始時間與結束時間，工作時間可能重疊，時間從$0$開始，開始與結束時間都是整數，有$n$台機器可以執行，每台機器同時間只可以執行一個工作，工作可以到每台機器去執行，且工作開始做就需要做完，機器執行中不能跳到另一個工作，可以一結束就馬上接著執行另一個工作，機器更換工作很快，可以不考慮切換所需時間，執行完後最少需要幾台機器才能完成所有工作？
### 輸入說明
每次輸入數字$n$，$n$表示需要執行的工作個數，輸入$n$小於$100$，之後有$n$行分別是每一行兩個整數$s$與$e$，$s$表示工作的開始時間與$e$表示工作的結束時間，且$s$永遠小於$e$。
### 輸出說明
輸出一個數字，表示需要幾台機器才能在指定的時間執行完所有工作。
### 輸入輸出範例
輸入範例
5
1 10
2 4
3 6
2 5
4 9
輸出範例
4
```cpp=
#include <iostream>
#include <algorithm> // for sort()
using namespace std;
typedef struct _job{
int start;
int end;
}JOB;
const int MAXN = 100+5; //最大的工作數量
JOB jobs[MAXN]; //儲存所有輸入工作的陣列
int endTimes[MAXN]; //紀錄所有運行中的工作結束時間
//自訂排序
//比較工作(結構)開始時間小的排前面
//若開始時間相同結束時間小的排前面
int cmp(JOB p, JOB q){
if(p.start==q.start) return(p.end<q.end);
else return (p.start<q.start);
}
//顯示陣列內容;驗證輸入資料
void showArray(int n)
{
for(int i=0;i<n;++i){
cout<<jobs[i].start<<" "<<jobs[i].end<<"\n";
}
}
int main()
{
//工作輸入: n筆工作
int n;
//不斷輸入n筆工作直到使用者按下ctrl+Z
while(cin>>n){
//將n筆工作讀入並存入陣列中
for(int i=0; i<n; i++){
cin>>jobs[i].start>>jobs[i].end;
}
sort(jobs, jobs+n, cmp);
showArray(n);
//Process:
int res=1; //第一台機器啟動
endTimes[0]=jobs[0].end;
//從第2個工作開始到最後一個工作判斷
//下一個工作的開始時間是否大於等於已經在運行的
//工作結束時間
bool found; //是否有找到沒在用的機器
for(int i=1; i<n; i++){
found = false;
for(int j=0; j<res; j++){
if(jobs[i].start>=endTimes[j]){ //判斷第i個工作開始時間是否大於等於第j個工作的結束時間
found = true; //找到空閒的機器
endTimes[j] = jobs[i].end; //重設工作結束時間
break;
}
}
if(!found){ //沒有空閒的機器
endTimes[res]=jobs[i].end;
res++;
}
}
cout<<res<<"\n";
}
return 0;
}
```
## 工作排程3
:::success
最小平均等待時間
:::
### 題目說明
有$n$個工作從開始就進入到機器，給予$n$個工作的執行需要的時間，只有一台機器可以執行，每次只能執行一個工作，且工作開始做就需要做完，機器執行中不能跳到另一個工作，請計算完成所有工作所需要的最小平均等待時間？
### 輸入說明
每次輸入數字$n$，$n$表示需要執行的工作個數，輸入$n$小於$100$，之後有$n$行分別是每一行一個整數$x$，$x$表示工作執行完成所需時間。
### 輸出說明
輸出一個浮點數，表示執行所有工作的最小平均等待時間。
### 輸入輸出範例
輸入範例
5
10
4
6
5
9
輸出範例
10.4
```cpp=
#include <iostream>
#include <algorithm> // for sort()
using namespace std;
const int MAXN = 100+5;//最大工作數量
int workTimes[MAXN]; //儲存輸入的每個完成所需的時間
int main()
{
int n;
while(cin>>n){
//資料輸入
for(int i=0; i<n; i++){
cin>>workTimes[i];
}
//資料處理
sort(workTimes, workTimes+n); //預設由小到大排序
int curTime=0; //紀錄目前執行時間
int waitTime=0; //紀錄等待執行時間
//從第i筆到n-1筆
for(int i=0; i<n-1; i++){
//第i個工作開始時間
//curTime += workTimes[i];
curTime = curTime + workTimes[i];
//累計等待時間
//waitTime += curTime;
waitTime = waitTime + curTime;
}
cout<<(double)waitTime/n<<"\n";
}
return 0;
}
```
## 工作排程4
:::success
有截止期限的最大利潤
:::
### 題目說明
假設剛開始有$n$個工作進入到機器，給予$n$個工作的截止時間與獲得的利潤，只有一台機器可以執行，每個工作都需花費一個單位時間執行，請計算在截止時間前如何安排工作執行，可以獲得最大利潤？
### 輸入說明
每次輸入數字$n$，$n$表示需要執行的工作個數，輸入$n$小於$100$，之後有$n$
行分別是每一行兩個整數
$x$與$income，x$表示工作的截止時間，而$income$表示執行該工作所獲得的利潤。
### 輸出說明
輸出一個整數，表示在截止時間前完成工作的最大利潤總和。
### 輸入輸出範例
輸入範例
5
2 10
3 4
1 5
2 7
3 8
輸出範例
25
```cpp=
#include <iostream>
#include <algorithm> // for sort()
using namespace std;
const int MAXN = 100+5;//最大工作數量
//自訂每個工作的型態
typedef struct _job{
int profit; //工作結束時間
int end; //工作利潤
}JOB;
JOB jobs[MAXN]; //記錄所有工作的陣列
JOB works[MAXN]; //紀錄已經選用的工作
//自訂排序比較
//工作利潤大的排前面
//若利潤相同,工作結束時間小的排前面
int cmp1(JOB p, JOB q)
{
if(p.profit==q.profit) return(p.end<q.end);
else return (p.profit>q.profit);
}
//自訂排序比較
//結束時間小的排前面
int cmp2(JOB p, JOB q)
{
return (p.end<q.end);
}
int main()
{
int n;
while(cin>>n){
for(int i=0; i<n; i++){
cin>>jobs[i].end>>jobs[i].profit;
}
//將工作利潤高的排前面
sort(jobs, jobs+n, cmp1);
//第1筆先選用
works[0] = jobs[0];
int counter=1; //紀錄已選用的筆數
//從第2個工作到第n個工作比對使否可以放置在已選用的陣列位置
for(int i=1; i<n; i++){
bool found = false; //紀錄是否找到已選用的空間
int idx; //在已選用陣列的索引位置
//依序比對所有已選的工作結束時間
for(idx=0; idx<counter; idx++ ){
//目前的工作結束時間(第i個)是否小於等於已選的工作結束時間
if(jobs[i].end<=works[idx].end){
found = true; //找到
break;
}
}
//找出應該放在的地方(考慮結束時間相同的狀態)
//有找到 //確保idx不會產生索引錯誤 // 目前工作結束時間與下一個工作結束時間相同
while(found && (idx<(counter-1)) && works[idx+1].end==works[idx].end){
idx++; //工作週期加1
}
//如果沒找到小於等於已選的工作結束時間
if(!found){
//直接將第i個工作加入已選的工作陣列中
works[counter] = jobs[i];
//已選的工作數量加1
counter++;
//已選的工作陣列以工作結束時間由小到大排序
sort(works, works+counter, cmp2);
}else if((idx+1) < jobs[i].end){
works[counter] = jobs[i];
//已選的工作數量加1
counter++;
//已選的工作陣列以工作結束時間由小到大排序
sort(works, works+counter, cmp2);
}
}
int res=0;
for(int i=0; i<counter; i++){
res = res + works[i].profit;
}
cout<<res<<"\n";
}
return 0;
}
```
Sign in with Wallet
Connect another wallet