# How to solve this job scheduling programming problem?

I am trying to solve this question. The question is a variation of job scheduling. There are n processes given to you with their execution time Ti and individual deadlines Di. A process can be executed anytime before its deadline. A process can not be executed after its deadline is over. So, you have to find the maximum number of processes that can be executed. Given that n <= 1000 and Ti & Di <= 1,000,000 For example:

Ti Di
3  4
4  8
11 23


I tried to solve this question using branch & bound mechanism. I first sort the processes on the basis of deadline. Then like 0/1 knapsack, I recursively took 2 cases. One is to take current process and other one is to discard this process. But the complexity of this approach is 2^n and it gave me TLE. Please suggest a better approach for this problem.

• what are your approaches? – SiluPanda Jun 7 '19 at 5:20
• Please give the reference to the original problem. – Optidad Jun 7 '19 at 7:24

I assume your question is "how many jobs can you achieve on time ?". The idea to use something like 0/1 knapsack is good. There is actually a DP resolution of 0/1 knapsack much more efficient than "recursively select or discard each item".

Let's call $$t_{max} = max(D[i])$$, the end horizon of your problem.

Create a vector $$A$$ of size $$t_{max}$$, $$A_i[t]$$ stands for the number of achieved jobs at time $$t$$ after considering all jobs until $$i^{th}$$ one. Initially, $$A_0$$ is filled with 0.

Then you loop on jobs, to build $$A_i$$ from $$A_{i-1}$$:

for t from D[i] to T[i] by -1:
A[t] = max(A[t], A[t-T[i]]+1)


Time complexity is $$O(Nt_{max})$$.

• Your approach is good but, I'm getting TLE. Since, number of test cases = 70 – Abhay Agarwal Jun 7 '19 at 10:45
• @Abhay_Agarwal What are you talking about ? TLE ? – Optidad Jun 7 '19 at 10:49
• Time Limit Exceed – Abhay Agarwal Jun 7 '19 at 10:51
• @Abhay_Agarwal Will you give the reference to the problem ? – Optidad Jun 7 '19 at 11:32