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. Please add a short paragraph explaining the approach at the beginning of the code to help us better understand and evaluate the solution. Also, try to keep the code readable (with comments) so that it is easier to evaluate the code correctness. Input Format Line 1: Space separated integers: n and K Line 2,...,n+1: Line i+1 lists the integer Ci Constraints 1 <= n <= 1000, 1 <= Ci <= 100000 Output Format Least number of days required to complete all the tasks on the first line. If the answer is D, then it should be followed by D lines where each line lists the tasks to be executed on that day. 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 4 2 3 5 Explanation All the tasks can be done in their original sequence in one day since two consecutive tasks have difference 3 (> 2). -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/90649970-8dc0-4bf9-bb0a-920e32193ace%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
