Minimum Cancellation Charge for Meetings

You are given \(K\) conference rooms and \(N\) meetings. Each meeting is assigned an index from \(1\) to \(N\) and is characterized by a starting time \(s_i\), an ending time \(e_i\) and a penalty \(w_i\) if cancelled.

The conference rooms operate under a very special rule. Two meetings \(i\) and \(j\) (if not cancelled) are considered related if at least one of the following conditions holds:

1. The intervals \([s_i, e_i]\) and \([s_j, e_j]\) have a nonempty intersection (touching at an endpoint is considered an intersection);
2. The intervals \([s_i, e_i]\) and \([s_j, e_j]\) do not intersect, but there exists another meeting \(c\) which is related to \(i\) and whose interval \([s_c, e_c]\) intersects \([s_j, e_j]\) (again, touching counts as an intersection).

Note that the definition of related meetings is evaluated only on the set of meetings that are not cancelled. Hence two meetings that were originally related may become unrelated if some meetings in between are cancelled.

All non-cancelled meetings must be assigned to a conference room, and any two related meetings must be assigned to different rooms. For example, for the three meetings \([1, 3]\), \([3, 5]\) and \([5, 7]\), although \([1, 3]\) and \([5, 7]\) do not intersect, they are indirectly related through \([3, 5]\) and thus must be assigned to different rooms.

Since there are only \(K\) rooms available, it might be necessary to cancel some meetings. Cancelling meeting \(i\) incurs a penalty cost of \(w_i\). Your task is to choose which meetings to cancel so that the conditions are satisfied while minimizing the total penalty cost.

For example, consider five meetings with intervals \([1,4], [3,6], [5,8], [7,10], [9,12]\) and penalties \(1,2,5,2,1\) respectively. With \(K=2\) conference rooms, one schedule may cancel the meeting \([5,8]\) for a penalty of \(5\), while another may cancel meetings \([3,6]\) and \([9,12]\) for a total penalty of \(3\). In this case the minimum total penalty is \(3\).

Implementation Details:

long long int min_charge(int K, vector<int> S, vector<int> E, vector<int> W)

The function min_charge will be called exactly once. The parameters are:

• K: Number of conference rooms available.
• S, E, W: Vectors of length \(N\). Meeting \(i+1\) (for \(0 \le i < N\)) starts at time S[i], ends at time E[i] and has a cancellation penalty of W[i].

Your submitted code must not contain any input/output function calls.

inputFormat

The input is given via arguments to the function min_charge:

• An integer K representing the number of conference rooms.
• A vector of integers S representing the start times of the meetings.
• A vector of integers E representing the end times of the meetings.
• A vector of integers W representing the penalty cost if each meeting is cancelled.

Note that \(N\), the number of meetings, is the size of any of the vectors S, E, or W.

outputFormat

Return a single integer representing the minimum total penalty cost incurred by cancelling meetings such that the remaining meetings can be scheduled in \(K\) conference rooms according to the rules described.

sample

K = 2
S = [1, 3, 5]
E = [3, 5, 7]
W = [1, 2, 1]

2