2244. Minimum Rounds to Complete All Tasks Medium

1/**
2 * [2244] Minimum Rounds to Complete All Tasks
3 *
4 * You are given a 0-indexed integer array tasks, where tasks[i] represents the difficulty level of a task. In each round, you can complete either 2 or 3 tasks of the same difficulty level.
5 * Return the minimum rounds required to complete all the tasks, or -1 if it is not possible to complete all the tasks.
6 *  
7 * Example 1:
8 *
9 * Input: tasks = [2,2,3,3,2,4,4,4,4,4]
10 * Output: 4
11 * Explanation: To complete all the tasks, a possible plan is:
12 * - In the first round, you complete 3 tasks of difficulty level 2.
13 * - In the second round, you complete 2 tasks of difficulty level 3.
14 * - In the third round, you complete 3 tasks of difficulty level 4.
15 * - In the fourth round, you complete 2 tasks of difficulty level 4.  
16 * It can be shown that all the tasks cannot be completed in fewer than 4 rounds, so the answer is 4.
17 *
18 * Example 2:
19 *
20 * Input: tasks = [2,3,3]
21 * Output: -1
22 * Explanation: There is only 1 task of difficulty level 2, but in each round, you can only complete either 2 or 3 tasks of the same difficulty level. Hence, you cannot complete all the tasks, and the answer is -1.
23 *
24 *  
25 * Constraints:
26 *
27 * 1 <= tasks.length <= 10^5
28 * 1 <= tasks[i] <= 10^9
29 *
30 */
31pub struct Solution {}
32
33// problem: https://leetcode.com/problems/minimum-rounds-to-complete-all-tasks/
34// discuss: https://leetcode.com/problems/minimum-rounds-to-complete-all-tasks/discuss/?currentPage=1&orderBy=most_votes&query=
35
36// submission codes start here
37use std::collections::HashMap;
38
39impl Solution {
40    pub fn minimum_rounds(tasks: Vec<i32>) -> i32 {
41        let mut map: HashMap<i32, i32> = HashMap::new();
42        for task in tasks {
43            let v = if let Some(t) = map.get(&task) {
44                *t + 1
45            } else {
46                1
47            };
48            map.insert(task, v);
49        }
50        let mut result = 0;
51        for m in map {
52            let (three, two, remain) = Self::greedy(m.1);
53            if remain != 0 {
54                return -1;
55            }
56
57            result += three + two;
58        }
59
60        result
61    }
62
63    // 3, 2, remains
64    fn greedy(i: i32) -> (i32, i32, i32) {
65        if i == 1 {
66            return (0, 0, 1);
67        } else if i % 3 == 0 {
68            return (i / 3, 0, 0);
69        } else if i % 3 == 2 {
70            return (i / 3, 1, 0);
71        } else {
72            return (i / 3 - 1, 2, 0);
73        }
74    }
75}
76
77// submission codes end
78
79#[cfg(test)]
80mod tests {
81    use super::*;
82
83    #[test]
84    fn test_2244() {
85        assert_eq!(
86            Solution::minimum_rounds(vec![2, 2, 3, 3, 2, 4, 4, 4, 4, 4]),
87            4
88        );
89        assert_eq!(Solution::minimum_rounds(vec![2, 33]), -1);
90    }
91}
92