1986. Minimum Number of Work Sessions to Finish the Tasks Medium

1/**
2 * [1986] Minimum Number of Work Sessions to Finish the Tasks
3 *
4 * There are n tasks assigned to you. The task times are represented as an integer array tasks of length n, where the i^th task takes tasks[i] hours to finish. A work session is when you work for at most sessionTime consecutive hours and then take a break.
5 * You should finish the given tasks in a way that satisfies the following conditions:
6 * 
7 * If you start a task in a work session, you must complete it in the same work session.
8 * You can start a new task immediately after finishing the previous one.
9 * You may complete the tasks in any order.
10 * 
11 * Given tasks and sessionTime, return the minimum number of work sessions needed to finish all the tasks following the conditions above.
12 * The tests are generated such that sessionTime is greater than or equal to the maximum element in tasks[i].
13 *  
14 * Example 1:
15 * 
16 * Input: tasks = [1,2,3], sessionTime = 3
17 * Output: 2
18 * Explanation: You can finish the tasks in two work sessions.
19 * - First work session: finish the first and the second tasks in 1 + 2 = 3 hours.
20 * - Second work session: finish the third task in 3 hours.
21 * 
22 * Example 2:
23 * 
24 * Input: tasks = [3,1,3,1,1], sessionTime = 8
25 * Output: 2
26 * Explanation: You can finish the tasks in two work sessions.
27 * - First work session: finish all the tasks except the last one in 3 + 1 + 3 + 1 = 8 hours.
28 * - Second work session: finish the last task in 1 hour.
29 * 
30 * Example 3:
31 * 
32 * Input: tasks = [1,2,3,4,5], sessionTime = 15
33 * Output: 1
34 * Explanation: You can finish all the tasks in one work session.
35 * 
36 *  
37 * Constraints:
38 * 
39 * n == tasks.length
40 * 1 <= n <= 14
41 * 1 <= tasks[i] <= 10
42 * max(tasks[i]) <= sessionTime <= 15
43 * 
44 */
45pub struct Solution {}
46
47// problem: https://leetcode.com/problems/minimum-number-of-work-sessions-to-finish-the-tasks/
48// discuss: https://leetcode.com/problems/minimum-number-of-work-sessions-to-finish-the-tasks/discuss/?currentPage=1&orderBy=most_votes&query=
49
50// submission codes start here
51
52use std::cmp;
53impl Solution {
54    pub fn min_sessions(tasks: Vec<i32>, session_time: i32) -> i32 {
55        let mut dp = vec![vec![-1; 16]; 1 << tasks.len()];
56        Self::help(&tasks, 0, 0, session_time, &mut dp)
57    }
58
59    fn help(tasks: &Vec<i32>, mask: i32, current: i32, session_time: i32, dp: &mut Vec<Vec<i32>>) -> i32 {
60        if current > session_time {
61            return i32::MAX;
62        }
63
64        if mask == (1 << tasks.len()) - 1 {
65            return 1;
66        }
67
68        if dp[mask as usize][current as usize] != -1 {
69            return dp[mask as usize][current as usize];
70        }
71
72        let mut result = i32::MAX;
73        for i in 0..tasks.len() {
74            if mask & (1 << i) == 0 {
75                let in_current = Self::help(tasks, mask | (1 << i), current + tasks[i], session_time, dp);
76                let in_next = 1 + Self::help(tasks, mask | (1 << i), tasks[i], session_time, dp);
77                result = cmp::min(result, cmp::min(in_current, in_next));
78            }
79        }
80
81        dp[mask as usize][current as usize] = result;
82        result
83    }
84}
85
86// submission codes end
87
88#[cfg(test)]
89mod tests {
90    use super::*;
91
92    #[test]
93    fn test_1986() {
94        assert_eq!(Solution::min_sessions(vec![3,1,3,1,1], 8), 2);
95    }
96}
97