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 4yr ago