SDE - 1

So basically its look hard - but its a tricky problem so basically I use difference idea,
1.arr[a] += k
arr[b+1] -= k
Because this “marks” the start of an increase at a, and the end of it after b.
2.Build final array using prefix sum
a) Traverse the array once, maintain a running sum.
b) The running sum at each point gives the actual value.
c) Keep track of the max while traversing.

So basically in my mind it strikes its a dp problem and need to define the states so I go through step by step
1.Define the states
dp[day][time] = maximum number of good wakeups possible starting from this state.
2. Transition (choices per day)
On day i, if current wake time = t:
Sleep for a[i] hours → new wake = (t + a[i]) % h.
OR delay → sleep for a[i] - 1 → new wake = (t + a[i] - 1) % h.
So I need to take the maximum of the two options.
and then just thought of base case and then code it

So initially - I replied simply sort it and the complexity was O(nlogn) they replied if it was so simple so why I should ask this question the expected time complexity is O(nlogk).
Then I think step by step and suddenly heap idea come to the mind because of the fact that The main idea is to sort the array efficiently from left to right. For each position i, we look at the next k elements (from i to i + k) and find the smallest element in that range using a min-heap.
We don’t need to look at elements to the left of i because they are already in their correct positions. By always placing the smallest available element at the current position, the array gets sorted efficiently as we move from left to right.
1: Initialize a Min-Heap
Create a min-heap to keep track of the next k+1 elements.
Because for the current position i, the smallest element that can go here will be somewhere in [i, i+k].
2: Fill the Initial Heap
Push the first k+1 elements of the array into the min-heap.
This ensures the heap contains all possible candidates for the first position.
3: Place the Smallest Element
Remove the smallest element from the min-heap and place it at position i in the array.
This guarantees that the current position is correctly sorted.
4: Slide the Window
Move to the next position i+1.
Add the next element from the array (at i+k+1) into the min-heap if it exists.
remove the smallest element from the heap and place it at i+1.
5: Repeat the process

We had 20 minutes discussion about that - interview was not satisfied with my answer.