Skip to content

17.16. The Masseuse

Description

A popular masseuse receives a sequence of back-to-back appointment requests and is debating which ones to accept. She needs a break between appointments and therefore she cannot accept any adjacent requests. Given a sequence of back-to-back appoint­ ment requests, find the optimal (highest total booked minutes) set the masseuse can honor. Return the number of minutes.

Note: This problem is slightly different from the original one in the book.

 

Example 1: 

Input:  [1,2,3,1]

Output:  4

Explanation:  Accept request 1 and 3, total minutes = 1 + 3 = 4

Example 2: 

Input:  [2,7,9,3,1]

Output:  12

Explanation:  Accept request 1, 3 and 5, total minutes = 2 + 9 + 1 = 12

Example 3: 

Input:  [2,1,4,5,3,1,1,3]

Output:  12

Explanation:  Accept request 1, 3, 5 and 8, total minutes = 2 + 4 + 3 + 3 = 12

Solutions

Solution 1

Thinking

Non-adjacent appointments, maximize total time — house robber. Recursion without memo repeats suffixes.

At \(i\) only two states matter: take it (so skip \(i-1\)) or skip it.

\(f\) takes the current, \(g\) skips it: roll \(f,g = g+x, \max(f,g)\). The answer is the larger, in constant space.

1
2
3
4
5
6
class Solution:
    def massage(self, nums: List[int]) -> int:
        f = g = 0
        for x in nums:
            f, g = g + x, max(f, g)
        return max(f, g)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public int massage(int[] nums) {
        int f = 0, g = 0;
        for (int x : nums) {
            int ff = g + x;
            int gg = Math.max(f, g);
            f = ff;
            g = gg;
        }
        return Math.max(f, g);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int massage(vector<int>& nums) {
        int f = 0, g = 0;
        for (int& x : nums) {
            int ff = g + x;
            int gg = max(f, g);
            f = ff;
            g = gg;
        }
        return max(f, g);
    }
};

1
2
3
4
5
6
7
func massage(nums []int) int {
    f, g := 0, 0
    for _, x := range nums {
        f, g = g+x, max(f, g)
    }
    return max(f, g)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function massage(nums: number[]): number {
    let f = 0,
        g = 0;
    for (const x of nums) {
        const ff = g + x;
        const gg = Math.max(f, g);
        f = ff;
        g = gg;
    }
    return Math.max(f, g);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    func massage(_ nums: [Int]) -> Int {
        var f = 0
        var g = 0

        for x in nums {
            let ff = g + x
            let gg = max(f, g)
            f = ff
            g = gg
        }

        return max(f, g)
    }
}

Comments