Minimum Penalty For a Shop

Leetcode Question Link

Analysis

Offset

The target is to find the time to achieve the smallest penalty, but not the penalty value itself. So the concrete value of penalty is not important, we could just focus on how penalty changes when changing shop closing time.

Let offset be the penalty diff when choosing closing time $i$ and closing time $0$, that is:

$$\text{offset}(i)=\text{penalty}(i)-\text{penalty}(0)$$

Moving Closing Time

Now let’s find how $\text{offset}(i)$ changes when $i:0\to n$.

---

When $i=0$, based on definition of offset, we have $\text{offset}(0)=0$

---

When we moving closing time $i$ from $k-1$ to $k$, discuss:

When at $k-1$ hour, there IS customers arriving. In this case, before moving closing time, there is an $Y$ in closing time, after moving, the $Y$ has been moved into open time. So $\text{offset}$ actually decrease by $1$ after moving.

When at $k-1$ hour, there IS NOT customers arriving. by similar analysis method, we know there is an $N$ moved from closing time to opening time, $\text{offset}$ increase by $1$.

Code Implementation

class Solution {
public:
    int bestClosingTime(string customers) {
        
        // init offset
        // at time 0, offset = 0
        int offset = 0, minOffset = 0;
        unsigned minTime = 0;
        bool arrived;
        
        int rangeEnd = customers.size() + 1;
        for (int i = 1; i < rangeEnd; ++i) {
        
            // check if there is customers arrived at previous time
            arrived = (customers[i - 1] == 'Y' ? 1 : 0);
            
            // someone arrived, then moving closing time
            // 1 hour later will cause offset decreasing by 1, 
            // otherwise, offset increasing by 1
            if (arrived)
                --offset;
            else
                ++offset;
 
            // update minOffset and minTime
            if (offset < minOffset) {
                minOffset = offset;
                minTime = i;
            }
        }
 
        return minTime;
    }
};