Optimal Sleep Schedule

Moderate

0/80

0 upvote

Asked in company

Problem statement

You are planning your sleep schedule for N consecutive days. The day has h hours, numbered 0 to h-1. For each day i (from 0 to N-1), you are given a required sleep duration a[i].

The process is as follows:

Your schedule starts on the morning of day 0, at hour 0.

On each day i, you begin your "sleep session" at the hour you woke up on that same day.

For your sleep session, you have two choices:

Sleep for exactly a[i] hours.

Sleep for a[i] - 1 hours.

Your wake-up time for the next day (i+1) is calculated as (starttime + sleepduration) % h.

There is a "good" interval of hours to wake up, from hour l to r inclusive. Your goal is to make a sequence of sleep duration choices to maximize the total number of times you wake up within this good interval.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains four space-separated integers: n, h, l, and r.

The second line contains n space-separated integers, representing the sleep durations a[0], a[1], ....

Output Format:

Print a single integer representing the maximum possible number of good wake-ups.

Note:

This problem has optimal substructure and overlapping subproblems, making it a perfect fit for Dynamic Programming.

Sample Input 1:

2 10 0 1
5 5

Sample Output 1:

Explanation for Sample 1:

Good interval is [0,1].
- Day 0 (start 0): Sleep 5 -> wake at 5 (Bad). Sleep 4 -> wake at 4 (Bad).
No matter what you choose on day 0, the next wake-up is bad. No path can yield any good wake-ups.

Sample Input 2:

2 10 3 5
4 1

Sample Output 2:

Explanation for Sample 2:

1. Day 0 (start 0): Choose to sleep `a[0]=4` hours. Wake up at hour 4 (Good). Good days = 1.
2. Day 1 (start 4): Choose to sleep `a[1]=1` hour. Wake up at `(4+1)%10 = 5` (Good). Good days = 2.
This path gives the maximum of 2 good wake-ups.

Expected Time Complexity:

The expected time complexity is O(N * H), where N is the number of days and H is the number of hours.

Constraints:

1 <= n <= 2000
2 <= h <= 2000
0 <= l <= r < h
1 <= a[i] < h

Time limit: 1 sec

Approaches (1)

Approach 1

Dynamic Programming

Time Complexity

Space Complexity

(100% EXP penalty)

Optimal Sleep Schedule

Console