algorithm - 如何在 : Given a Hotel and checkin/Checkout time of visitors, 找到所需的最少房间数

Question

假设我得到一个作为 (checkin, checkout) 传递的未排序元组的列表，我需要返回我需要的最小房间数以避免冲突。到目前为止，我想到了:

 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

你的算法坏了。正确的做法是制作一个事件列表，然后先按时间排序，然后在 checkin 前 checkout 。现在我们进行如下:

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