Maximum Usable Cable Length
A workshop has several cable rolls. The length of each roll is given in cableRolls.
Select any number of rolls and cut them into exactly segmentCount non-empty segments.
The longest half of the segments fail inspection. Return the maximum total length of the remaining segments.
Maximum Usable Cable Length
Implement the following method:
int maximumUsableCableLength( List<Integer> cableRolls, int segmentCount )
cableRolls contains the length of every available cable roll.segmentCount is the exact number of segments to create.- The method returns the maximum total length that can pass inspection.
Cutting Rules
- Every segment must have a positive integer length.
- Each segment must come from exactly one cable roll.
- Parts from different rolls cannot be joined into one segment.
- A roll may be cut into multiple segments.
- If a roll is selected, its entire length must be used.
- Some cable rolls may remain unused.
Inspection Rules
- Exactly
segmentCount / 2 longest segments fail inspection.
- The remaining
segmentCount / 2 segments pass inspection.
- If equal-length segments occur at the inspection boundary, any of them may fail because the resulting usable total remains the same.
Constraints
1 ≤ cableRolls.size() ≤ 1,0000 ≤ cableRolls.get(i) ≤ 1,000 for every 0 ≤ i < cableRolls.size().2 ≤ segmentCount ≤ 1,000segmentCount is even.- The sum of all values in
cableRolls is at least segmentCount.
- It is always possible to create exactly
segmentCount non-empty segments.
- The result fits in a Java
int.
Examples
Example 1
maximumUsableCableLength( cableRolls = [6, 10, 11], segmentCount = 4 )
Output: 11
Keep the rolls of lengths 6 and 10 unchanged. Cut the roll of length 11 into segments of lengths 5 and 6.
The sorted segment lengths are [5, 6, 6, 10]. The two longest segments fail, leaving a usable total of 5 + 6 = 11.
Example 2
maximumUsableCableLength( cableRolls = [9], segmentCount = 6 )
Output: 3
Cut the roll into segments with lengths [1, 1, 1, 2, 2, 2]. The three longest segments fail, and the other three have a total length of 3.
Example 3
maximumUsableCableLength( cableRolls = [0, 5, 9], segmentCount = 4 )
Output: 6
Leave the zero-length roll unused. Keep the roll of length 5 unchanged and cut the roll of length 9 into three segments of length 3.
The sorted segment lengths are [3, 3, 3, 5]. After the two longest segments fail, the usable total is 3 + 3 = 6.
Example 4
maximumUsableCableLength( cableRolls = [7, 10, 13], segmentCount = 4 )
Output: 13
Keep the rolls of lengths 7 and 10 unchanged. Cut the roll of length 13 into segments of lengths 6 and 7.
The sorted segment lengths are [6, 7, 7, 10]. The remaining segments have a maximum total length of 6 + 7 = 13.