如何：给定酒店和访客的入住/退房时间，找到所需的最小房间数

Question

假设我得到一个作为（签入，签出）传入的未排序元组列表，我需要返回所需的最小房间数，以避免冲突。到目前为止，我想：

 sort by checkout time
 room = 1 
 for each checkout time
    if there exists checkout time < checkin 
        room += 1
    end if 
 end for
 return room

排序需要nlogn运行时间（n），这相当于O（nlgn），我能做得更好吗？我想我可能有我没有处理过的角落案件，但我想不出有什么。

这是一个面试问题。有什么帮助吗？

Answer 1

你的算法坏了。一个正确的方法是列出一个事件列表，然后先按时间对它们进行排序，然后在签入前结帐。现在我们如下所示：

max_rooms = 0
rooms = 0
for each event
    if event.type == checkin
        rooms += 1
        if max_rooms < rooms
            max_rooms = rooms
        end if
    else
        rooms -= 1
    end if
end for
return max_rooms