ProgramSchedule
SRM 231 · 2005-02-19 · by lars2520
SRM 231 · 2005-02-19 · by lars2520 · Greedy, Sorting
Problem Statement
Problem Statement
So much to do and so little time to do it in! You have a long list of
computer programs that must be run and you want them to finish running
as soon as possible. Each program in the list requires a certain
amount of your time to set up, and during this time you must devote
your full attention to the setup of that program. After you have
finished with the setup of a program, it will immediately start
execution and will run for a certain amount of time on the computer.
You have enough processing power that all of the programs may be run
simultaneously without any of them slowing down. You are to find a
schedule such that the time at which all of the programs are finished
is as early as possible and you should return that time (assuming you
start at time 0).
You will be givenint[] 's A and B,
corresponding elements of which represent a single program. Each
element of A represents the setup time of a program and the
corresponding element of B represents the running time of that
program.
You will be given
Constraints
- A and B will contain the same number of elements.
- A and B will contain between 1 and 50 elements, inclusive.
- Each element of A and B will be between 1 and 1000, inclusive.
Examples
0)
{1,2,3,4}
{2,2,4,2}
Returns: 12
In this case, you can simply execute the programs in the same order they are given (though there are other ways which give the same final time). The 4 programs will finish after 3, 5, 10, and 12, respectively.
1)
{3,1,2}
{4,3,9}
Returns: 11
2)
{1000}
{1000}
Returns: 2000
3)
{654,13,89,651,67,3,21,654,312}
{56,3,56,651,897,32,654,897,321}
Returns: 2504
4)
{56,3,56,651,897,32,654,897,321}
{654,13,89,651,67,3,21,654,312}
Returns: 3570
Submissions are judged against all 75 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ProgramSchedule with a public method int schedule(vector<int> A, vector<int> B) · 75 test cases · 2 s / 256 MB per case