slrohit's blog

By slrohit, history, 8 years ago, In English

Need Help How to solve below problem with nlogn complexity, I tried to solve it using dfs but getting wrong answer

There are n tasks (T1,...,Tn) that need to be executed exactly once. Each task requires the use of a common equipment in such a way that on a given day, Ti can be completed if and only if no task Tj (j > i) has been completed on that day. In other words, the set of tasks completed on each day must have increasing indices. An additional constraint is imposed because of task categories: each task Ti belongs to category Ci, and tasks Ti, Tj cannot be scheduled consecutively on a particular day if they belong to nearby categories, i.e., if |Ci — Cj| <= K. What is the smallest number of days needed to complete all the tasks? Also output the indexes of the tasks that should be executed on each day.

Constraints 1 <= n <= 1000, 1 <= Ci <= 100000

Sample Input

5 2 15 9 12 15 18

Sample Output

1 1 2 3 4 5

Sample Input

5 3 1 2 7 5 2

Sample Output

2 1 5 2 7 2

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it