本文的翻译是专门为“开发人员算法”课程的学生准备的。
本文是有关如何解决算法问题的系列文章的一部分。 根据我的个人经验，我发现大多数资源只是简单地详细描述了解决方案。 不幸的是，对能够找到有效解决方案的推理主线的解释不是很普遍。 因此，本系列文章的目的是描述从头解决问题的可能推理过程。
挑战赛
酒店经理必须在下一个季节处理N个预订单。 他的酒店有K间客房。 预订信息包含入住日期和退房日期。 经理想找出酒店中是否有足够的房间来满足需求。
输入数据：
-第一个输入有关到达时间信息的列表
-第二-包含出发时间信息的列表
-第三-K，表示房间数
输出数据：
-表示预订房间能力的逻辑值
false表示该酒店没有足够的房间来预订N
true表示酒店有足够的房间可预订N次
一个例子：
输入数据：
-签到= [1、3、5]
-出发= [2，6，10]
-K = 1
输出：false。 一天= 5，酒店有2位客人。 但是我们只有一个号码。
决策过程
在我看来，这项任务很有趣，因为有许多不同的解决方法。 让我们看一下选项。
每天存储计数器的结构
第一个想法可能是我们需要一种结构来存储每天的订单数量。 该结构可以是具有固定大小（由最长出发日期确定）的数组。
输入数据：
-条目= [1、3、5]
-离场= [2，6，10]
-k = 1
对于此示例，数组的大小将为10（因为第10天的最后一个出口）。 为了填充此数组，我们浏览了进入和退出列表，并增加或减少了相应日期的计数器。 伪代码示例：
int[] counts = new int[maxDepartures(departures)] for each arr in arrivals { counts[arr]++ } for each dep in departures { counts[dep]-- }
结果，我们得到以下数组：
: 1 0 1 1 2 1 1 1 1 0
: 1 2 3 4 5 6 7 8 9 10阵列装满后，只需检查一下所有元素是否不超过
k （房间数）即可。
在前面的示例中，最大房间数为1。由于在第5天有2个预订，因此返回
false 。
此解决方案的时间复杂度为O（n），其中n为预留数，空间为O（m），其中m为最大出发日。 从理论上讲还不错，但是它可能会为一个大型数组分配很多内存，尽管其中大部分不会被使用。
例如：
输入数据：
-条目= [1、3、5]
-出发次数= [2，10000，10]
-k = 1
在这种情况下，将分配一万个整数的数组。
让我们看看其他解决方案。
事件收集存储
还有什么其他选择？ 让我们再次看看以前的结构发生了什么：
: 1 0 1 1 2 1 1 1 1 0
: 1 2 3 4 5 6 7 8 9 10我们看到一些信息是重复的。 例如，在6到9天之间，预订数量没有变化，因为我们知道在这段时间内什么也不会发生。
如果存储事件，会更好吗？ 让我们再次以相同的示例：
输入数据：
-条目= [1、3、5]
-离场= [2，6，10]
第一天：+1预订
第2天：-1预订
第3天：+1预订
第6天：-1预订
第5天：+1预订
第10天：-1预订
解决方案是遍历这些事件以增加或减少计数器。 如果在某个时候计数器大于
k ，则返回
false 。 但是，为了进行迭代，需要对事件的集合进行排序。
在这里最好使用哪种结构？ 让我们总结一下我们的要求：
- 搜索以检查是否已经存在这一天
- 添加新的一天，
- 查看结构以在每个排序的日期进行迭代。
如何使用二叉搜索树（BST）？
每个节点可以表示如下：
class Node { int day int count Node left Node right }
排序将在
day字段中完成。
让我们看一下时间复杂度的后果：
- 搜索以检查是否已经存在这样的日子：一般情况下为O（log（n）），最坏情况下为O（n），
- 添加新的一天：一般情况下为O（log（n）），最坏情况下为O（n），
- 查看用于在每个排序的日期进行迭代的结构：使用深度搜索的O（n）。
由于我们必须遍历每个元素并将其插入树中，因此算法的复杂度通常为O（n log（n）），最坏情况为O（n²）。
另一种选择是在添加所有事件之后使用哈希表并对键进行排序：
- 搜索以检查是否已经存在这样的一天：一般情况下为O（1），最坏情况下为O（n）（概率取决于关联数组的容量），
- 添加新的一天：一般情况下为O（1），最坏情况下为O（n），
- 查看用于遍历每个已排序日期的结构：O（n log（n））用于排序关键字，O（n）用于排序。
最后，解决方案在中间情况下（归因于排序操作）为O（n log（n）），在最坏情况下为O（n²）。 该解决方案似乎与基于树的解决方案具有相同的复杂性。
让我们看一下Java中使用排序关联数组的可能实现：
public boolean hotel(ArrayList<Integer> arrivals, ArrayList<Integer> departures, int k) { // Map<Integer, Integer> events = new HashMap<>(); // int n = arrivals.size(); for (int i = 0; i < n; i++) { int arrival = arrivals.get(i); int departure = departures.get(i); // Integer current = events.get(arrival); events.put(arrival, current == null ? 1 : current + 1); // current = events.get(departure); events.put(departure, current == null ? -1 : current - 1); } // Map<Integer, Integer> sortedEvents = new TreeMap<>(events); int count = 0; for (Map.Entry<Integer, Integer> entry : sortedEvents.entrySet()) { count += entry.getValue(); // count if (count > k) { return false; } } return true; }
恒定的空间复杂度
如果要优化算法，则需要考虑是否真的需要存储所有这些事件？ 我们不能仅对收集数据（进入和退出）进行排序并检查预订限制吗？
一种解决方案是可能的，但是为此，有必要通过预先排序来简化输入数据。
如果两个集合都已排序，我们可以使用两个指针（一个用于入口，另一个用于出口）简单地遍历每个元素，并动态检查限制。
如您所见，在每次迭代过程中，我们仍然需要检查
arrivals.get(indexArrival) departures.get(indexDeparture)之间的最小值，以找出需要更新的指针。
通常，由于排序操作，该算法具有恒定的时间和空间复杂度O（n log（n））。