Minimum number of work sessions to finish the tasks

Array Dynamic Programming Backtracking Bit Manipulation Bitmask

34.6% acceptance

Feb 25, 2026

1185

There are n tasks assigned to you. The task times are represented as an integer array tasks of length n, where the ith 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. You should finish the given tasks in a way that satisfies the following conditions: If you start a task in a work session, you must complete it in the same work session. You can start a new task immediately after finishing the previous one. You may complete the tasks in any order. Given tasks and sessionTime, return the minimum number of work sessions needed to finish all the tasks following the conditions above. The tests are generated such that sessionTime is greater than or equal to the maximum element in tasks[i].

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_sessions(tasks: Vec<i32>, session_time: i32) -> i32 {
    let n = tasks.len();
    let total_masks = 1 << n;
    
    // Precompute sum for each subset
    let mut subset_sum = vec![0i32; total_masks];
    for mask in 0..total_masks {
      for i in 0..n {
        if mask & (1 << i) != 0 {
          subset_sum[mask] = subset_sum[mask ^ (1 << i)] + tasks[i];
          break;
        }
      }
    }
    
    // dp[mask] = minimum sessions to complete tasks in mask
    let mut dp = vec![n as i32 + 1; total_masks];
    dp[0] = 0;
    
    for mask in 1..total_masks {
      // Enumerate all submasks of mask
      let mut sub = mask;
      while sub > 0 {
        if subset_sum[sub] <= session_time {
          dp[mask] = dp[mask].min(dp[mask ^ sub] + 1);
        }
        sub = (sub - 1) & mask;
      }
    }
    
    dp[total_masks - 1]
  }
}