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 &lt;= 1000 and Ti &amp; Di &lt;= 1,000,000 For example:

Ti Di
3  4
4  8
11 23


Answer = 3

I tried to solve this question using branch &amp; 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.
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})$.