Introduction
This blog will discuss the approach to calculate the minimum number of days to debug all programs. Before jumping on the approach of the problem to calculate the minimum number of days to debug all programs, let’s first understand the problem,
In this problem, we need to return the minimum number of days required to debug all programs. We’ll be given the array which consists of the time to debug a particular program and an integer value which states the time of the working session. Working Session states the atmost time which one can consecutively devote and then take a break. In this, if that time is less than 6 hours then we can complete two working sessions in one day otherwise only one working session per day and it is also given that maximum number of jobs at any time is less than or equal to 14.
For Example:
Input:-
codeTime[] = {1,2,3,1,1,3}
Working session time:- 4
Output:-
2
Explanation:-
We can complete the first and third task in the first working session, the fourth and sixth tasks in the second working session, and the second and fifth tasks in a third working session.
Therefore, 2 working days as working sessions time is less than 6, so we can opt for two working sessions in one day, therefore a minimum of 2 days are required to debug all programs.
Approach
The approach of this question is to consider all the possible subsets, and then find the minimum number of days among them. To implement this we will try to do this for each job, either try to put them in the current session, and make a new session for each job, and then take the minimum of both of the cases. There are many overlapping subproblems, so to optimize this we will dp array to store the values of the already processed elements.
Steps of Algorithm
Step 1. Make a boolean array of size n, to store which elements are processed, and which are not. We will denote processed elements as true, and not processed elements as false.
Step 2. Make a dp array of size [1<<14][15], because at max, we can have 14 jobs, and initialize all with -1.
Step 3. We will try to process each job in the current session, make a new session for each job, and return a minimum of both the answer.
Step 4. We can include the task in the current session if the remaining time is greater than the time of that particular task, and then we need to update the remaining time. If not greater than the time of that task, then create a new session and increment the number of sessions.
Step 5. We will convert the boolean array into an integer by calling boolTonumber, as this denotes the current state of the processed elements, and will check in the dp array if it was already processed or not.
Step 6. Base case will be, when all the elements are processed, we will check this using the isProcessed array, if it contains all try, we simply return 1.
Step 7: After calculating all the sessions, we will find number of days, by comparing the sessionTime, if it greater than 6, then number of session = number of days, otherwise,if session time is less than 6, then if number of sessions are odd, number of days = (number of sessions/2) + 1, else number of days = (number of sessions/2).
Implementation in C++
#include<bits/stdc++.h>
using namespace std;
// function to check if all elements are processed or not
// if everything is true, then return true
// as all elements are processed otherwise return false
bool check(vector < bool > & isProcessed, int n) {
for (int i = 0; i < n; i++) {
if (isProcessed[i] == false) return false;
}
return true;
}
// convertung the boolean array into number
// so to check and save the current state into the dp array
int boolToNumber(vector < bool > & isProcessed, int n) {
int ans = 0;
for (int i = 0; i < n; i++) {
if (isProcessed[i] == true) {
ans += pow(2, i);
}
}
return ans;
}
// function to find out the minimum sessions to complete all the job
int solve(int codeTime[], int n, int currTime, int sessionTime, vector < bool > & isProcessed, vector < vector < int >> & dp) {
if (currTime > sessionTime) return 1e9;
// if all are processed
if (check(isProcessed, n)) return 1;
int mask = boolToNumber(isProcessed, n);
// checking the current state is already processed or not
if (dp[mask][currTime] != -1) return dp[mask][currTime];
int ans = 1e9;
for (int i = 0; i < n; i++) {
if (isProcessed[i] == false) {
// mark as processed
isProcessed[i] = true;
// try to include in the current session
int include = solve(codeTime, n, currTime + codeTime[i], sessionTime, isProcessed, dp);
// make new session
int notInclude = 1 + solve(codeTime, n, codeTime[i], sessionTime, isProcessed, dp);
// again mark as unprocessed to explore the other paths
isProcessed[i] = false;
// cout << ans << " ";
ans = min(ans, min(include, notInclude));
}
}
return dp[mask][currTime] = ans;
}
int main() {
int codeTime[] = {1, 2, 3, 1, 1, 3};
int n = 4;
int sessionTime = 3;
vector < bool > isProcessed(n, false);
vector < vector < int >> dp(1 << 15, vector < int > (15, -1));
int numberOfsessions = solve(codeTime, n, 0, sessionTime, isProcessed, dp);
int ans;
// if session time is less than 6.
// calulate the number of days
if (sessionTime < 6) {
if (numberOfsessions % 2 == 0) {
ans = numberOfsessions / 2
} else {
ans = numberOfsessions / 2 + 1;
}
} else {
ans = numberOfsessions;
}
cout << "Minimum number of days required : " << ans << endl;
}
Output:
Minimum number of days required: 2
Complexity Analysis
Time Complexity: O(2 ^ N * SessionTime * N)
Incall to ‘getResult()’, we are calculating for each task in the array which is of size ‘N’, and then we are calculating the minimum sessions, therefore the overall time complexity is O(2 ^ N * SessionTime * N), where ‘N’ is the size of the ‘time_input’ vector.
Space Complexity: O(2 ^ N * SessionTime)
As we are using a DP table of at max ‘2 ^ N * SessionTime’ size, therefore, the overall space complexity will be O(2 ^ N * SessionTime).