# 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.

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;

}

}

Last modified 3yr ago