資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究活動選擇問題
有 n 項不同的活動，給出了它們的開始時間和結束時間。選擇由一個人解決的活動數量上限。我們將使用貪心演算法找到剩餘活動中結束時間最短、開始時間大於等於上次選擇的活動的結束時間的下一項活動。
- 當清單未排序時，此問題的複雜度為 O(n log n)。
- 當提供已排序的清單時，複雜度為 O(n)。
輸入和輸出
Input:
A list of different activities with starting and ending times.
{(5,9), (1,2), (3,4), (0,6), (5,7), (8,9)}
Output:
Selected Activities are:
Activity: 0 , Start: 1 End: 2
Activity: 1 , Start: 3 End: 4
Activity: 3 , Start: 5 End: 7
Activity: 5 , Start: 8 End: 9演算法
maxActivity(act, size)
輸入：活動列表，列表中的元素數量。
輸出 − 選取了如何執行活動的順序。
Begin initially sort the given activity List set i := 1 display the ith activity //in this case it is the first activity for j := 1 to n-1 do if start time of act[j] >= end of act[i] then display the jth activity i := j done End
示例
#include<iostream>
#include<algorithm>
using namespace std;
struct Activitiy {
int start, end;
};
bool comp(Activitiy act1, Activitiy act2) {
return (act1.end < act2.end);
}
void maxActivity(Activitiy act[], int n) {
sort(act, act+n, comp); //sort activities using compare function
cout << "Selected Activities are: " << endl;
int i = 0;// first activity as 0 is selected
cout << "Activity: " << i << " , Start: " <<act[i].start << " End:
" << act[i].end <<endl;
for (int j = 1; j < n; j++) { //for all other activities
if (act[j].start >= act[i].end) { //when start time is >= end
time, print the activity
cout << "Activity: " << j << " , Start: " <<act[j].start << " End: " << act[j].end <<endl;
i = j;
}
}
}
int main() {
Activitiy actArr[] = {{5,9},{1,2},{3,4},{0,6},{5,7},{8,9}};
int n = 6;
maxActivity(actArr,n);
return 0;
}輸出
Selected Activities are: Activity: 0 , Start: 1 End: 2 Activity: 1 , Start: 3 End: 4 Activity: 3 , Start: 5 End: 7 Activity: 5 , Start: 8 End: 9
更新於：15-6-2020
4 千次瀏覽
廣告