Maximize Party Planning Reward

Question

You are asked to be an organizer for n parties and are provided with their start and end times. (For example: P1: 7 AM - 9 AM; P2: 8 AM to 3 PM; P3: 4 AM to 8 AM.) You can only be organizing one party at a time, so you need to choose. For every party that you organize, you are given a fixed reward (1000$) irrespective of the length of the party. How do you select the parties to maximize your reward? What is the time complexity of your algorithm in terms of n?

Answer 1

sort(time.end)

res=1

current_end= interval[0].end;

for(i is 1 to n)

if(interval[i]_start <current_end)

current_end=min(current_end, interval[i].end)

}

else res++

current_end=interval[i].end

Answer 2

Suppose parties are given by their start and end times as: [[s1, e1], [s2, e2], .... [sn, en]]

We can see there is an optimal schedule with non-overlapping party time.

Proof :  Assume that there is no optimal schedule with non-overlapping that includes the first ending party.

 suppose an optimal schedule is given as S. We construct a schedule S’ as follows:

 remove the very first ending party in S and add the first ending party overall, which consists of interval [s1, e1].

We observe that S’ is a feasible schedule. Further S’ schedules as many parties as the given optimal schedule S. Further S’ includes the first ending one. This contradicts the assumption that there is no optimal schedule with non-overlapping parties that includes the first ending party.

 we can simply sort them by their end time and iterate the parties as following steps:

step1. Sort the parties by increasing end times using O(n log n) time

step2. Initialize ending time of selected party in O(1) time

step3. For j = 1 to n

If j-th  starts after the ending time, then: Select j​-th  and update ending time, else skip which takes O(n) time

Thus, the overall algorithm runs in O(n log n) time.