5

我在这个问题上挣扎了这么久。

在酒店有 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 卢比。所以我们必须实现一个可以找到最大利润值的算法。假设人们只需要早上 5 点到晚上 11 点的房间，并且每个人都想要几个小时后的房间。

输入说明：

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

输出说明：

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

例子：

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

产量：
2000

4

3 回答 3

6

这是间隔调度问题。

可以通过按结束时间对区间进行排序，先贪婪地选择最早的deadline，去掉所有重叠的区间并重复来解决。

于 2015-05-03T08:51:18.983 回答
3

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

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

于 2015-05-03T08:56:42.657 回答
1

以下是您问题的确切解决方案：

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

?>
于 2015-10-14T12:15:31.863 回答