Following is the problem statement.
You are given n activities with their start and finish times. Select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a time.
Example:
Example 1 : Consider the following 3 activities sorted by
by finish time.
start[] = {10, 12, 20};
finish[] = {20, 25, 30};
A person can perform at most two activities. The
maximum set of activities that can be executed
is {0, 2} [ These are indexes in start[] and
finish[] ]
Example 2 : Consider the following 6 activities
sorted by by finish time.
start[] = {1, 3, 0, 5, 8, 5};
finish[] = {2, 4, 6, 7, 9, 9};
A person can perform at most four activities. The
maximum set of activities that can be executed
is {0, 1, 3, 4} [ These are indexes in start[] and
finish[] ]
The greedy choice is to always pick the next activity whose finish time is least among the remaining activities and the start time is more than or equal to the finish time of previously selected activity. We can sort the activities according to their finishing time so that we always consider the next activity as minimum finishing time activity.
1) Sort the activities according to their finishing time
2) Select the first activity from the sorted array and print it.
3) Do following for remaining activities in the sorted array.
…….a) If the start time of this activity is greater than or equal to the finish time of previously selected activity then select this activity and print it.
In the following C implementation, it is assumed that the activities are already sorted according to their finish time
没有合适的资源?快使用搜索试试~ 我知道了~
ACM-ACM-ICPC算法示例之Greedy-题解.zip
共28个文件
cpp:12个
java:8个
md:6个
需积分: 5 0 下载量 49 浏览量
2024-02-25
20:25:54
上传
评论
收藏 27KB ZIP 举报
温馨提示
ACM_ACM-ICPC算法示例之Greedy_题解
资源推荐
资源详情
资源评论
收起资源包目录
ACM_ACM-ICPC算法示例之Greedy_题解.zip (28个子文件)
ACM_ACM-ICPC算法示例之Greedy_题解
MinimumCoins
MinimumNumOfCoins.java 1KB
mincoins.cpp 780B
ContainerShip
containerShip.cpp 1KB
README.md 346B
MaximumIncreasingSubarray
ProblemStatement.md 328B
MaximumIncreasingSubarray.cpp 540B
Greedy_Graph_Coloring
GreedyGraphColoring.cpp 3KB
OddSumSubsequence
ProblemStatement.md 532B
OddSumSubsequence.cpp 523B
ActivitySelection
Activity_Selection.py 1KB
ActivitySel.cpp 1KB
ActivitySelection.java 2KB
README.md 2KB
MinNoOfBrackets
MinimumSwapOfBracket.java 1KB
Kruskal’sMinimumSpanningTree
Kruskal’sMinimumSpanningTree.java 5KB
Kruskal’sMinimumSpanningTree.py 1KB
Kruskal’sMinimumSpanningTree.cpp 3KB
Gas Station
containerShip.cpp 777B
README.md 1KB
EqualizingBitStrings
EqualizeBitStrings.cpp 614B
README.md 576B
Knapsack
newknapsak.java 649B
0-1_Knapsackproblem.cpp 861B
Fractional_Knapsack.cpp 1KB
Greedy01KnapsackSolver.java 3KB
frac_knapsack.java 2KB
Huffman coding
huffman coding.java 4KB
huffman.cpp 2KB
共 28 条
- 1
资源评论
m0_57195758
- 粉丝: 719
- 资源: 243
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功