I am new to Algorithms and Competitive Coding. I read an exercise paper given by my teacher as below:
The director of a hospital want to schedule a working plan for a nurse in a given period of N consecutive days 1,..., N. Due to the policy of the hospital, each nurse cannot work all the days 1,..., N. Instead, there must be days off in which the nurse need to take a rest. A working plan is a sequence of disjoint working periods. A working period of a nurse is defined to be a sequence of consecutive days on which the nurse must work and the length of the working period is the number of consecutive days of that working period. The hospital imposes two constraints:
Each nurse can take a rest only one day between two consecutive working periods. it means that if the nurse takes a rest today, then she has to work tomorrow (1)
The length of each working period must be greater or equal to K1 and less than or equal to K2 (2)
The director of the hospital want to know how many possible working plans satisfying above constraint?
6 2 3
I have thought a lot and just give an initial idea: I will use an 1-D array to represent a schedule from day 1 to day N. for each day (ith day), I have two choices: the nurse will work this day or the nurse will not work on this day.
If the nurse does not work on the ith day, the ways for this case is the total ways of the ith-2 day. (Because she must have a day off on the previous day.
Else, the ways for this case will be the sum of total ways of the ith-j day, with j in [K1, K2].
However, I do not know why I am wrong and which way will be the correct answer. I really need your help to derive an appropriate algorithm