标签: maximum-profit-problem

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

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

通过观察上图,我们可以很容易地看到经理最多只能容纳两个人(第1和第3或第1和第4或第2和第3或第2和第4).因此,他可以获得的最大利润是500 + 500 = 1000卢比.所以我们必须实现一个可以找到最大利润值的算法.假设人们只想在凌晨5点到晚上11点之间的房间,并且每个人在多个小时内想要房间.

输入说明:

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

输出说明:

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

例:

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

产出:
2000