Interval planning algorithm or activity selection algorithm

Question

I have been struggling with this issue for so long.

The hotel has Russian people who want to have the same room. Everyone wants to stay at the hotel at a time convenient for him, but only one person can stay at a time. Suppose the room is available from 5am to 11pm. The hotel management accepts 500 rupees from each person who is in this room. It doesn't matter how long a person stays in this room. We must maximize the profit of the manager. We say that n = 4, i.e. Four people want the same room. Let's say the 1st person wants a room from 6 AM to 8 AM, and the second person wants a room from 7 AM to 8 AM, the third person wants a room from 8 AM to 12 PM, and the fourth person wants a room from 11 AM to 1 PM.

By observing the above figure, we can easily see that the manager can allow a maximum of two people to stay (1st and 3rd, 1st and 4th, 2nd, 3rd, 2nd and 4th d). Thus, the maximum profit that he can get is 500 + 500 = 1000 rupees. Thus, we must implement an algorithm that can find the maximum value of profit. Suppose that people only want a room from 5 AM to 11 PM, and everyone wants a room in a few hours.

Input Description:

{<1st start time> # <1st end time>, <2nd start time → <2nd end of a person>, ............, #}

Output Description:

The output should be the maximum value of profit.
For the example discussed in question, output 2000.

Example:

Entrance:
{6 AM # 8 AM.11AM # 1 PM.7AM # 3 PM.7AM # 10 AM.10AM # 12 PM.2PM # 4 PM.1PM # 4 PM.8AM # 9AM}

Conclusion:
2000

Answer 1

It looks like a variant of the problem of choosing activity.

Read this TopCoder Tutorial for a great explanation.

Answer 2

This is an interim planning task .

You can solve it by sorting the intervals by the end time and eagerly select the earliest deadline, delete all overlapping intervals and repeat.

Answer 3

Below is the exact solution for your question:

<?php // Timezone set date_default_timezone_set("Asia/Kolkata"); // User - i/p $input = "{6AM#8AM,11AM#1PM,7AM#3PM,7AM#10AM,10AM#12PM,2PM#4PM,1PM#4PM,8AM#9AM}"; // Processing i/p string to ARRAY $input_array = []; // Array given as i/p to "calculateprofit"-function $processed_array = (explode(',', substr($input, 1, -1))); foreach ($processed_array as $key => $value) $input_array[] = explode("#", $value); // Function call and display o/p $maximim_profit = calculateprofit($input_array); echo "<strong>Input</strong> = ".$input; echo "<br/><br/><strong>Maximum Profit</strong> = ".$maximim_profit; // Function to calculate - Maximum Profit function calculateprofit($input){ $room_charges = 500; $members_covered = [$input[0]]; $last_member = 0; $finishing_time = array(); foreach ($input as $key => $row) $finishing_time[$key] = date("H:i", strtotime($row[1])); array_multisort($finishing_time, SORT_ASC, $input); for($i=1; $i<sizeof($input); $i++){ $current_coustmer = $input[$i]; if(date("H:i", strtotime($current_coustmer[0])) >= date("H:i", strtotime($input[$last_member][1])) ){ $members_covered[] = $input[$i]; $last_member = $i; } } // print_r($members_covered); return sizeof($members_covered)*$room_charges; } ?>