patternMinor
Solving road trip problem in linear time
Viewed 0 times
problemsolvinglineartimetriproad
Problem
Consider the following problem:
You are on a road trip, and there are $n$ cities along a road, labeled
$1$ to $n$. Conveniently, these cities all lie on a single road, and
the distance between two adjacent cities is one mile. We are currently
at city $1$, and would like to drive to city $n$. Each day, we can
drive at most $k$ miles, before we sleep for the night. We pay $a_i$
for lodging at the city located at mile $i$. Each lodging cost is a
positive number. Given that we can spend an arbitrary number of days
on the road trip, determine a plan of driving to minimize lodging
costs.
Input: An integer $k$, and a length $n$ array of positive integers
$a_1,...,a_n$.
Output: The minimum lodging cost to complete the road trip starting
from city 1 and ending at city n.
The most trivial way of solving this problem is to adapt the well-known dynamic programming algorithm for computing the longest increasing subsequence of an array. This requires $n$ iterations and at each iteration, we must compute the minimum of the previous $k$ values, due to the restriction on distance driven per day. This yields an algorithm of time complexity $O(nk)$.
I'm wondering...is there a way to solve this problem in only $O(n)$ time? My intuition is telling me that there is a way to not have to check $k$ prior values at each iteration. Does anyone have an idea?
You are on a road trip, and there are $n$ cities along a road, labeled
$1$ to $n$. Conveniently, these cities all lie on a single road, and
the distance between two adjacent cities is one mile. We are currently
at city $1$, and would like to drive to city $n$. Each day, we can
drive at most $k$ miles, before we sleep for the night. We pay $a_i$
for lodging at the city located at mile $i$. Each lodging cost is a
positive number. Given that we can spend an arbitrary number of days
on the road trip, determine a plan of driving to minimize lodging
costs.
Input: An integer $k$, and a length $n$ array of positive integers
$a_1,...,a_n$.
Output: The minimum lodging cost to complete the road trip starting
from city 1 and ending at city n.
The most trivial way of solving this problem is to adapt the well-known dynamic programming algorithm for computing the longest increasing subsequence of an array. This requires $n$ iterations and at each iteration, we must compute the minimum of the previous $k$ values, due to the restriction on distance driven per day. This yields an algorithm of time complexity $O(nk)$.
I'm wondering...is there a way to solve this problem in only $O(n)$ time? My intuition is telling me that there is a way to not have to check $k$ prior values at each iteration. Does anyone have an idea?
Solution
This problem can be solved in $O(n)$ time, using a min-queue. We can build a data structure that has enqueue, dequeue and get-min operations that all work in amortized $O(1)$ time (rather than $\Omega(\log n)$ time as greybeard seems to think).
Building a min-stack (pop, push, get-min) that does these operations in $O(1)$ time is easy (keep track of the previous minimum in a separate stack when the minimum changes due to a push, so that we can use this secondary stack to restore the previous minimum when the current minimum gets popped). To build a min-queue, we can use the classical construction that builds a queue (with amortised $O(1)$ operations) from two stacks.
The $O(nk)$ dynamic programming algorithm can be modified using the min-queue to run in $O(n)$ time.
Building a min-stack (pop, push, get-min) that does these operations in $O(1)$ time is easy (keep track of the previous minimum in a separate stack when the minimum changes due to a push, so that we can use this secondary stack to restore the previous minimum when the current minimum gets popped). To build a min-queue, we can use the classical construction that builds a queue (with amortised $O(1)$ operations) from two stacks.
The $O(nk)$ dynamic programming algorithm can be modified using the min-queue to run in $O(n)$ time.
Context
StackExchange Computer Science Q#40580, answer score: 6
Revisions (0)
No revisions yet.