Problem Statement |
| |
You are programming the process scheduler for an operating system that controls many processors. The parallelism achieved by this new system is total, meaning that any number of processes can run at the same time without disturbing each other. Of course, certain processes may need some other processes to end before they start.
You will be given the execution time of each process as a int[], where the ith element is the number of milliseconds the ith process takes to complete execution. The information about precedences will be given as a String[] prec, where the jth character of the ith element is 'Y' if process j needs process i to be finished before executing itself and 'N' otherwise. Return the minimum number of milliseconds needed for all processes to be finished. If it's impossible for all the processes to finish, return -1.
|
| |
Definition |
| | | Class: | ParallelProgramming | | Method: | minTime | | Parameters: | int[], String[] | | Returns: | int | | Method signature: | int minTime(int[] time, String[] prec) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | time will contain between 1 and 50 elements, inclusive. |
| - | time and prec will contain the same number of elements. |
| - | Each element of time will be between 1 and 1000, inclusive. |
| - | Each element of prec will contain exactly N characters, where N is the number of elements in prec. |
| - | Each element of prec will contain only 'N' and 'Y'. |
| - | The ith character of the ith element of prec will be 'N'. |
| |
Examples |
| 0) | |
| | {150,200,250} | {"NNN",
"NNN",
"NNN"} |
| Returns: 250 | | In this case, all processes can run in parallel, so after 250 milliseconds, they will all finish. |
|
|
| 1) | |
| | {150,200,250} | {"NNN",
"YNN",
"NNN"} |
| Returns: 350 | | In this case, process 0 has to wait for process 1 to end, so the finishing time of process 0 cannot be sooner than 350. Process 2 can execute at any time during those 350 milliseconds because it has no precedence relationships. |
|
|
| 2) | |
| | {150,200,250} | {"NYN",
"NNY",
"NNN"} |
| Returns: 600 | | In this case there is no parallelism, so the three processes need to be executed in the sequence 0-1-2. |
|
|
| 3) | |
| | {150,200,250} | {"NYN",
"NNY",
"YNN"} |
| Returns: -1 | | No process can begin execution here because all of them are waiting for another process to finish. Therefore, it is impossible for all of the processes to finish. |
|
|
| 4) | |
| | {345,335,325,350,321,620} | {"NNNNNN",
"NNYYYY",
"YNNNNN",
"NNYNYN",
"NNNNNN",
"NNNNNN"} |
| Returns: 1355 | |
|