TwoMonthScheduling | Topcoder Archive

Problem Statement

There is a sequence of pending jobs. Each job depends on all previous jobs. If job B depends on job A, job B cannot be started before job A (but they can be started at the same time).

The total number of workers you have available is workers. Each job takes two months to complete, and must be completed in two consecutive months. Job i demands firstMonth[i] workers during the first month and secondMonth[i] workers during the second month.

Compute and return the smallest number of months in which all jobs can be completed.

Use the pseudocode below to generate firstMonth[] and secondMonth[]:

L0, L1 = length(firstMonth0), length(firstMonth1)
for i1 in 0 .. L1-1:
    for i0 in 0 .. L0-1:
        firstMonth [ i1 * L0 + i0 ] = min( workers,  firstMonth0[i0] xor  firstMonth1[i1] )
        secondMonth[ i1 * L0 + i0 ] = min( workers, secondMonth0[i0] xor secondMonth1[i1] )

Definition

Class:: TwoMonthScheduling
Method:: minimumMonths
Parameters:: int, int[], int[], int[], int[]
Returns:: int
Method signature:: int minimumMonths(int workers, int[] firstMonth0, int[] firstMonth1, int[] secondMonth0, int[] secondMonth1)
(be sure your method is public)

Notes

The reference solution does not depend on the input format, it would correctly solve any input of the size allowed by the constraints.
The elements of the arrays firstMonth and secondMonth do not exceed the number of workers you have. Thus, a solution always exists.

Constraints

workers will be between 1 and 10^9, inclusive.
firstMonth0 will have between 1 and 500 elements, inclusive.
firstMonth1 will have between 1 and 10 elements, inclusive.
secondMonth0 will have the same number of elements as firstMonth0.
secondMonth1 will have the same number of elements as firstMonth1.
Each element of the four arrays will be between 0 and 10^9, inclusive.

Examples

```
1000
```
```
{900, 150, 300, 200}
```
```
{0}
```
```
{400, 300, 600, 150}
```
```
{0}
```
```
Returns: 4
```
The arrays firstMonth0 and secondMonth0 are identical to the generated arrays firstMonth and secondMonth. An optimal solution looks as follows: month 1: first month of job 0 (900 workers needed) month 2: second month of job 0, first month of job 1 (400 + 150 workers needed) month 3: second month of job 1, first month of jobs 2 and 3 (300 + 300 + 200 workers needed) month 4: second month of jobs 2 and 3 (600 + 50 workers needed)
```
1000
```
```
{900, 150, 300, 200}
```
```
{0}
```
```
{400, 600, 300, 150}
```
```
{0}
```
```
Returns: 5
```
The input looks similar to Example 0, but job 1 now requires more and job 2 requires fewer workers during their second months. Even though the sum of times is still the same, it is no longer possible to do everything in four months.
```
1000
```
```
{350, 172, 24}
```
```
{998, 54}
```
```
{513, 119, 0}
```
```
{24, 118}
```
```
Returns: 7
```
The arrays you are supposed to generate: firstMonth = {696, 842, 1000, 360, 154, 46} secondMonth = {537, 111, 24, 631, 1, 118}
```
47
```
```
{0,0,0,0,0,0,1,0,0,0}
```
```
{0,0,0,0,0,0,0,0,0,0}
```
```
{0,0,0,0,0,0,0,0,0,0}
```
```
{0,0,0,0,0,0,1,0,0,0}
```
```
Returns: 2
```
A lot of jobs, but most of them require no workers at all. All these jobs can be done at the same time.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.