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;
    }
}