HeroicScheduled2
SRM 726 · 2017-12-18 · by subscriber
SRM 726 · 2017-12-18 · by subscriber · Dynamic Programming
Problem Statement
Problem Statement
Hero has a list of tasks he can do.
Each task will take him exactly one day, and on each day he can only work on one of the tasks.
The days on which Hero can do these tasks are numbered starting from 0.
Each task i has two parameters: start[i] is the first day on which Hero can do this task, and finish[i] is the last such day.
Hero can choose which tasks he will perform and in which order.
Note that he is not required to maximize the number of tasks he'll complete.
In particular, he can always choose not to do any of the tasks.
You are given the int[] s start and finish.
Calculate and return the number of different subsets of tasks Hero may complete.
Constraints
- start and finish will contain the same number of elements.
- start will contain between 1 and 50 elements, inclusive.
- Each element in finish will be between 0 and 15, inclusive.
- For each i start[i] will be between 0 and finish[i], inclusive.
Examples
0)
{0,0,0}
{0,0,0}
Returns: 4
Hero will either do nothing or he will complete one of the three tasks.
1)
{14,14,14}
{15,15,15}
Returns: 7
This time Hero has two days, and on each of them he can complete one of the three given tasks. Thus, he can complete any set of zero, one, or two tasks, but not all three of them.
2)
{0,0,1,2,3,4}
{0,1,2,3,4,4}
Returns: 63
3)
{0,1,2,2}
{3,2,2,2}
Returns: 12
4)
{0,0,0,2,2,2,3,3,3}
{1,2,3,3,4,5,3,4,5}
Returns: 427
Submissions are judged against all 83 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class HeroicScheduled2 with a public method long long getcount(vector<int> start, vector<int> finish) · 83 test cases · 2 s / 256 MB per case