Minimum Sheet Cutting Time
A factory has metal sheets that must be cut using laser machines. The cutting grade required by each sheet is given in sheetGrades.
The maximum grade supported by each laser is given in laserRatings. A laser can cut a sheet when the required grade is less than or equal to its rating.
Cutting a sheet takes one second. A laser must then cool for one second before cutting another sheet. All lasers can operate simultaneously.
Return the minimum time needed to cut every sheet. Return -1 if completing all sheets is impossible.
Minimum Sheet Cutting Time
Implement the following method:
int minimumCuttingTime( List<Integer> sheetGrades, List<Integer> laserRatings )
sheetGrades contains the required cutting grade of every sheet.laserRatings contains the maximum supported grade of every laser.- The method returns the minimum elapsed time, or
-1 when some sheet cannot be cut.
Cutting Rules
- Every sheet must be cut exactly once.
- A laser can cut at most one sheet at a time.
- Cutting one sheet takes exactly one second.
- After cutting a sheet, the laser must cool for one full second before starting another sheet.
- Cooling is not required after a laser completes its final sheet.
- Every laser is available at the beginning.
- Different lasers may cut sheets at the same time.
Constraints
1 ≤ sheetGrades.size() ≤ 100,0001 ≤ laserRatings.size() ≤ 100,000 1 ≤ sheetGrades.get(i) ≤ 1,000,000,000 1 ≤ laserRatings.get(i) ≤ 1,000,000,000
Examples
Example 1
minimumCuttingTime( sheetGrades = [5, 9, 4, 7, 3, 2], laserRatings = [5, 9, 7] )
Output: 3
Each laser can cut two suitable sheets. Every laser cuts one sheet, cools for one second, and cuts its second sheet. All six sheets are completed after three seconds.
Example 2
minimumCuttingTime( sheetGrades = [12, 12, 12, 12, 2, 2], laserRatings = [12, 5, 5] )
Output: 7
Only the laser rated 12 can cut the four grade-12 sheets. Four cutting seconds and three cooling seconds are required.
Example 3
minimumCuttingTime( sheetGrades = [6, 4, 1, 5], laserRatings = [6] )
Output: 7
The single laser cuts all four sheets. It requires four cutting seconds and three cooling seconds.
Example 4
minimumCuttingTime( sheetGrades = [8, 3, 5], laserRatings = [7, 6] )
Output: -1
Neither laser supports the sheet requiring grade 8.
Example 5
minimumCuttingTime( sheetGrades = [4, 7, 2, 6], laserRatings = [4, 7, 3, 6] )
Output: 1
Each sheet can be assigned to a different suitable laser, so all sheets are cut during the first second.