有n项工作,每项工作分别在si时间开始,在ti时间结束。对于每项工作,你都可以选择参与与否。如果选择了参与,那么自始至终都必须全程参与。此外,参与工作的时间段不能重叠(即使是开始与结束的瞬间重叠也是不允许的)。
你的目标是参与尽可能多的工作,那么最多能参与多少项工作呢?1<=n<=100000,1<=si<=ti<=10^9。
有n项工作,每项工作分别在si时间开始,在ti时间结束。对于每项工作,你都可以选择参与与否。如果选择了参与,那么自始至终都必须全程参与。此外,参与工作的时间段不能重叠(即使是开始与结束的瞬间重叠也是不允许的)。
你的目标是参与尽可能多的工作,那么最多能参与多少项工作呢?1<=n<=100000,1<=si<=ti<=10^9。
3
5 20
14 17
8 11
2
(1)在可选的工作中,每次都选取开始时间最早的工作
(2)在可选的工作中,每次都选取结束时间最早的工作
(3)在可选的工作中,每次都选取用时最短的工作
(4)在可选的工作中,每次都选取与最少可选工作有重叠的工作
此问题可通过贪心算法求解,关键在于对上述贪心策略的选择
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部cnt: 39693
关于网站改版