leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

minimum-number-of-work-sessions.dart (1646B)

      1 //This is my solution to the minimum work sessions problem using
      2 //DFS and backtracking. The goal is to find the minimum number of sessions
      3 //to completed the tasks where you can not split task time between multiple sessions
      4 //and the length of each session is sessionTime.
      5 //This gives a TLE because it is very brute force.
      6 
      7 class Solution {
      8   int minSessions(List<int> tasks, int sessionTime) {
      9       Map<int,int> vals = {};
     10       for(int i = 0; i < tasks.length ; ++i){
     11           vals[tasks[i]] = (vals[tasks[i]] ?? 0) + 1;
     12       }
     13       int sessions = (vals[sessionTime] ?? 0);
     14       Map<String,int> memo = {};
     15       tasks.sort();
     16       tasks = tasks.sublist(0,tasks.length - sessions);
     17       return minSess(tasks , sessionTime, 0,sessions);
     18   }
     19   int minSess(List<int> tasks , int sessionTime, int currentTime, int sessions){
     20       if(tasks.length == 0){
     21           return sessions;
     22       }
     23       int ret_val = 1000000000;
     24       for(int i = 0 ; i < tasks.length ; ++i){
     25           if(tasks[i] > currentTime){
     26               List<int> new_tasks = List.from(tasks);
     27               new_tasks.removeAt(i);
     28               int current = minSess(new_tasks, sessionTime, sessionTime - tasks[i] , sessions + 1);
     29               if(current < ret_val){
     30                   ret_val = current;
     31               }
     32           }
     33           else{
     34               List<int> new_tasks = List.from(tasks);
     35               new_tasks.removeAt(i);
     36               int current = minSess(new_tasks, sessionTime, currentTime - tasks[i] , sessions);
     37               if(current < ret_val){
     38                   ret_val = current;
     39               }
     40           }
     41       }
     42       return ret_val;
     43   }
     44 }