Алгоритм интервального планирования или алгоритм выбора активности

Question

Алгоритм интервального планирования или алгоритм выбора активности

Я так долго борюсь с этим вопросом.

Есть n человек, которые хотят одну и ту же комнату в отеле. Каждый человек хочет остаться в отеле в удобное для него время, но одновременно может остаться только один человек. Предположим, что комната доступна с 5 утра до 11 вечера. Менеджер отеля получает 500 рупий с каждого человека, который останавливается в этом номере. Неважно, как долго человек находится в этой комнате. Мы должны максимизировать прибыль менеджера. Допустим, что n = 4, то есть четыре человека хотят одну комнату. Допустим, что 1-й человек хочет комнату с 6 до 8, а 2-й человек хочет с 7 до 8, 3-й человек хочет с 8 до 12, а 4-й хочет с 11 до 13.

введите описание изображения здесь

Наблюдая за рисунком выше, мы можем легко увидеть, что менеджер может разрешить пребывание максимум двух человек (1-го и 3-го или 1-го и 4-го или 2-го и 3-го или 2-го и 4-го). Таким образом, максимальная прибыль, которую он может получить, составляет 500 + 500 = 1000 рупий. Поэтому мы должны реализовать алгоритм, который может найти максимальное значение прибыли. Предположим, что люди хотят комнату только с 5 утра до 11 вечера, и каждый человек хочет комнату в несколько часов.

Описание ввода:

{<1-е лицо время начала> #<Время окончания первого лица>,<Время начала 2-го человека> #<Время окончания второго человека>, …………, #}

Описание выхода:

На выходе должно быть максимальное значение прибыли.
Для примера, рассмотренного в вопросе, результат равен 2000.

Пример:

Входные данные:
{6} AM#8AM,11AM#1PM,7AM#3PM,7AM#10AM,10AM#12PM,2PM#4PM,1PM#4PM,8AM#9AM

Выход:
2000

5

algorithm logic maximum-profit-problem php

Решение

Другие решения

Это Проблема планирования интервалов.

Это можно решить, отсортировав интервалы по времени окончания и выбрав жадно сначала самый ранний срок, удалите все перекрывающиеся интервалы и повторите.

6

Ниже приводится точное решение для вашего вопроса:

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

?>

1

Источник

Accepted Answer

Похоже, вариант задачи выбора деятельности.

Прочитай это Учебник по TopCoder за отличное объяснение.

3