0
$\begingroup$

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

Answer = 3

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.

$\endgroup$
  • 1
    $\begingroup$ what are your approaches? $\endgroup$ – SiluPanda Jun 7 at 5:20
  • 1
    $\begingroup$ Please give the reference to the original problem. $\endgroup$ – Vince Jun 7 at 7:24
1
$\begingroup$

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})$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.