Graph, DAG problem

Revision ru1, by slrohit, 2017-04-11 11:15:44

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru1 Russian slrohit 2017-04-11 11:15:44 1052 Первая редакция перевода на Русский
en1 English slrohit 2017-04-09 11:26:04 1052 Initial revision (published)