区间调度算法或Activity选择算法

Question

这个问题我纠结了好久

酒店有n个人要同一个房间。每个人都想在自己方便的时间入住酒店，但一次只能入住一个人。假设房间从早上 5 点到晚上 11 点可用。酒店经理从入住该房间的每个人那里收取 500 卢比。一个人在那个房间里呆多久并不重要。我们必须最大化经理的利润。假设 n = 4，即四个人想要同一个房间。假设第一个人想要早上 6 点到早上 8 点的房间，第二个人想要早上 7 点到早上 8 点的房间，第三个人想要早上 8 点到中午 12 点的房间，第四个人想要上午 11 点到下午 1 点的房间。

通过观察上图，我们很容易看出经理最多只能允许两个人入住（1st and 3rd or 1st and 4th or 2nd and 3rd or 2nd and 4th）。所以他可以获得的最大利润是 500+500 = 1000 卢比。所以我们必须实现一个可以找到最大利润值的算法。假设这些人只在 b/w 早上 5 点到晚上 11 点想要房间，并且每个人在多个小时内想要房间。

输入说明：

{<第一人称开始时间>#<第一人称结束时间>,<第二人称开始时间>#<第二人称结束时间>,…………,#}

输出描述：

输出应该是最大利润值。
对于问题中考虑的示例，输出为 2000。

示例：

输入：
{6AM#8AM,11AM#1PM,7AM#3PM,7AM#10AM,10AM#12PM,2PM#4PM,1PM#4PM ,8AM#9AM}

输出：
2000

Answer 1

这是Interval Scheduling Problem。

可以通过按结束时间对间隔进行排序，并选择greedily最早的截止时间优先，删除所有重叠间隔并重复来解决。

Answer 2

看起来像是 Activity 选择问题的变体。

阅读此 TopCoder Tutorial 以获得出色的解释。

Answer 3

以下是您问题的准确答案：

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

?>

区间调度算法或Activity选择算法

Interval Scheduling Algorithm or Activity Selection Algorithm

php

algorithm

logic

maximum-profit-problem