592. Rounds of Two or Three
A repair crew has a backlog of jobs, and tasks[i] is the difficulty level of job i. The crew works in rounds. In a single round it must finish exactly 2 jobs or exactly 3 jobs, and all jobs finished in that round must share the same difficulty level.
Return the minimum number of rounds needed to finish every job, or -1 if some job can never be scheduled under these rules. Jobs of different difficulty levels never interact, so only how many jobs exist at each level matters. Your solution should run in O(n) expected time with O(n) extra space.
Example 1
- Input:
- tasks = [5,5,5,8,8]
- Output:
- 2
- Explanation:
The three 5s take one round of 3 and the two 8s take one round of 2, giving 2 rounds.
Example 2
- Input:
- tasks = [4,4,4,4,4,4,4]
- Output:
- 3
- Explanation:
Seven equal jobs split as 3 + 2 + 2 which is 3 rounds, and 2 rounds cannot cover seven jobs.
Example 3
- Input:
- tasks = [1,2,2]
- Output:
- -1
- Explanation:
The single job of level 1 can never be grouped, so the answer is -1.
Constraints
1 ≤ tasks.length ≤ 2000000 ≤ tasks[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 3,200 msC++ 800 msJava 1,600 msJavaScript 1,600 msTypeScript 1,600 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)