P6092 [CEOI 2012] Work Planning

CEOI received $M$ tasks over $N$ days. Each task needs $1$ machine working for $1$ day to be completed. CEOI has many machines, and each machine can complete at most one task per day. CEOI requires that each task can be delayed by at most $D$ days. In other words, if a customer submits a task on day $S$, CEOI must finish it by day $S + D$. Please write a program to find the minimum number of machines needed to complete all tasks on time, under the constraint that each task can be delayed by at most $D$ days.

The first line contains three integers: $N$ is the number of days during which CEOI receives tasks, $D$ is the maximum number of days each task can be delayed, and $M$ is the number of tasks. The second line contains $M$ integers separated by spaces. The $i$-th number represents the day when the $i$-th task is received. There are no tasks after day $N - D$. All tasks are numbered from $1$ to $N$ in order of the input.

Output one integer, the minimum number of machines that can complete the tasks.

For $50\%$ of the testdata, $M \le 10^5$. For all testdata, $1 \le N \le 10^5$, $0 \le D < N$, $1 \le M < 10^6$. Translated by ChatGPT 5