> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/coding_practice_questions/hard/the-masseuse.md).

# The Masseuse

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

```
EXAMPLE
Input {30, 15, 60, 75, 45, 15, 15, 45}
Output180 minutes ({30, 60,45, 45}).
```

**Complexity:** O(n) time and space\
**The Idea:** Create an interval for each allocated time frame. Add an extra 15 minutes to make them adjacently overlapping. Then run this through weighted interval scheduling algorithm. With a trace back solution, we can find the optimal schedules that maximize booking times.

```cpp
vector<Schedule> masseuse_max_bookings(const vector<int> & appointments) {
    vector<Schedule> s;
    s.reserve(appointments.size());
    int prev = 0;
    for (const int i : appointments) {
        int acc_next = i + prev;
        s.emplace_back(prev, acc_next + 15);
        prev = acc_next;
    }
    vector<int> sol1 = interval_scheduling(s);
    vector<Schedule> sol2;
    for (int i : sol1) {
        sol2.push_back(s[i]);
    }
    return sol2;
}

int main()
{
    vector<int> bookings = { 30, 15, 60, 75, 45, 15, 15, 45 };
    vector<Schedule> sol = masseuse_max_bookings(bookings);
    int acc_sum = 0;
    for (auto i : sol) {
        acc_sum += i.weight - 15;
        cout << "(" << i.start << ", " << i.end << ")" << " -> " << acc_sum << endl;
    }
}
```