This pair of problems evaluates algorithmic problem-solving skills, focusing on spatial optimization with Manhattan distances for grid-based demand aggregation and sequential penalty minimization on binary time-series data, emphasizing reasoning about aggregation and trade-offs.
You are given an M x N grid grid containing only 0 and 1.
grid[r][c] = 1
means there is demand at cell
(r, c)
(e.g., a customer/home).
grid[r][c] = 0
means no demand.
1
cell).
Goal: Choose the store location that minimizes the total distance from every demand cell (1) to the store.
grid
:
M x N
matrix of 0/1.
1
s, the minimum total distance is
0
.
You are given a string customers of length n consisting only of 'Y' and 'N'.
customers[i] = 'Y'
means at hour
i
at least one customer arrives.
customers[i] = 'N'
means no customers arrive at hour
i
.
A shop chooses a closing time t where t is an integer in [0, n]:
[0, t-1]
.
[t, n-1]
.
The penalty is:
customers[i] = 'N'
(wasted open hour)
customers[i] = 'Y'
(missed customer hour)
Task: Return the earliest closing time t that achieves the minimum penalty.
customers
: string of
'Y'
/
'N'
t
(earliest minimizer).