求计算城镇内同时最大人数的最优算法：现有O(n log n)解法可优化吗？

问题背景 #

给定n个人员的进出城镇日期对(aᵢ, bᵢ)：

• aᵢ是第i个人的进入日期（当日凌晨抵达城镇）
• bᵢ是第i个人的离开日期（当日深夜离开城镇）
• 示例：若某人4日进入、12日离开，实际在城镇停留9天

需要找到同一时间点城镇内的最大人数，要求算法尽可能高效。

我的实现思路 #

我目前想到的解法步骤如下：

• 拆分输入列表，将所有进入日期存入数组arrivals，所有离开日期存入数组departures
• 对两个数组分别做升序排序
• 使用双指针遍历两个数组：
  • 若arrivals[i] <= departures[j]，说明有新人进入城镇，计数器count += 1，同时移动进入数组的指针i += 1
  • 否则说明有人离开城镇，计数器count -= 1，同时移动离开数组的指针j += 1
  • 每完成一次指针移动，就更新最大人数（取当前计数器值与历史最大值的较大值）
• 最终输出记录的最大人数

该算法的时间复杂度为O(n log n)，主要耗时在排序环节。

疑问 #

是否存在比O(n log n)更高效的解法？比如时间复杂度能达到O(n)的方案？

内容的提问来源于stack exchange，提问作者Mia