Interval Scheduling Algorithm or Activity Selection Algorithm

Question

I'm struggling with this question for so long.

There are n persons who want same room in a hotel. Each person wants to stay in the hotel for his own convenient time but only one person can stay at a time. Assume that room is available from 5AM to 11PM. Hotel manager takes 500 rupees from each person who is staying in that room. It does not matter how long a person stays in that room. We have to maximize the profit of the manager. Let us say that n =4 i.e. four persons want same room. Let us say that 1st person wants the room from 6AM to 8AM and 2nd person wants room from 7AM to 8AM, 3rd person wants room from 8AM to 12PM and 4th person wants room from 11AM to 1PM.

By observing above figure, we can easily see that manager can only allow maximum of two persons to stay (1st and 3rd or 1st and 4th or 2nd and 3rd or 2nd and 4th). So maximum profit he can get is 500+500 = 1000 rupees. So we have to implement an algorithm which can find maximum profit value. Assume that the persons want the room only b/w 5AM to 11PM and each person wants room in multiple of hours.

Input description:

{<1st person starting time>#<1st person ending time>,<2nd person starting time>#<2nd person ending time>,…………, # }

Output description:

Output should be maximum profit value.
For the example considered in the question, output is 2000.

Example:

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

Output:
2000

Answer 1

Looks like a variant of the Activity Selection Problem.

Read this TopCoder Tutorial for an excellent explanation.

Answer 2

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

?>

Answer 3

This is Interval Scheduling Problem.

It can be solved by sorting the intervals by end time, and choosing greedily the earliest deadline first, remove all overlapping intervals and repeat.