Minimum Days to Release All Updates in Order
Problem statement
A mobile app has $n$ updates to ship. For update $i$, $\text{planned}[i]$ is its scheduled launch day and $\text{alternate}[i]$ is an earlier fallback day. Updates must go live in non-decreasing order of their planned dates; updates that share a planned date may go live in any order among themselves. Each update launches on either its planned day or its alternate day, and several updates may share a day. An alternate day that has already passed -- earlier than the day the previous update went live -- cannot be used. Return the minimum possible day on which the last update ships.
Example: $n = 4$, $\text{planned} = [3, 7, 4, 9]$, $\text{alternate} = [1, 5, 2, 3]$. In planned-date order the updates are $[1, 3, 2, 4]$. Ship update 1 on day 1 (alternate), update 3 on day 2 (alternate), update 2 on day 5 (alternate), and update 4 on day 9 (its alternate day 3 has already passed, so fall back to the planned day). The last ship day is $9$, so return $9$.
Show hint
If ship days can only move forward in release order, what does it buy you to ship each update as early as it legally can?
Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.