CODEWITHSUNDEEP
algorithm
segue_segway
segue_segway

Reputation: 1518

Comparing my algorithm solution with the textbook

I'm working on a problem out of Cracking the Coding Interview that goes as follows:

A popular masseuse receives a sequence of back-to-back appointment requests and is debating which ones to accept. She needs a 15-minute break between appointments and therefore she cannot accept any adjacent requests. Given a sequence of back-to-back appointment requests (all multiples of 15 minutes, non overlap, and none can be moved), find the optimal (highest total booked minutes) set the masseuse can honour. Return the number of minutes.

Examples

Input : {30, 15, 60, 75, 45, 15, 15, 45} Output : 180 minutes ({30, 60, 45, 45})

Input: [75, 105, 120, 75, 90, 135] Output: [75, 120, 135]

My recursive solution revolved around the following:

Therefore, every element has the choice to skip by two or skip by 3.

The textbook recursive solution worked as follows:

Is my algorithm incorrect in some way? Or is it just an equally optimal way of proceeding through the problem? Shouldn't both algorithms be O(2^N) without memoization, and O(N) with memoizing?

Upvotes: 2

Views: 236

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

Your algorithm is correct though more complicated. It doesn't consider every single subset without adjacent elements, but the ones it doesn't consider are not maximal and hence not optimal because the appointment times should all be positive.

The running time of the given solution without memoization is more precisely Theta(Fib(n)) where Fib(n) is the nth Fibonacci number (about O(1.62^n)). The recurrence for yours is either

T(n) = T(n-2) + T(n-3) + T(n-4)

or

T(n) = T(n-2) + 2 T(n-3) + T(n-4)

depending on whether you reuse the computation of maxVal(index + 3). The former implementation runs in time about O(1.47^n); the latter, O(1.72^n).

Upvotes: 1

Related Questions