从一组约会中获取重叠时间范围的列表 [英] Get a list of overlapping time ranges from a set of appointments
问题描述
标题不是很好，我愿意接受建议。
Title isn't great, and I'm open to suggestions.
这是我的基本问题：
我有一组约会，每个约会都有开始时间和结束时间。
I have a set of appointments, each with a start time and end time.
鉴于该设置，我想要的是一组新的范围 [开始时间，结束时间] ，用于所有重复约会 n 的时段。
Given that set, what I want is a new set of ranges [ start_time, end_time ] for all periods where there are n overlapping appointments.
因此，例如，给定集合（为简化可读性，时间戳简化为小数字）
So, for example, given the set (timestamps simplified to small numbers for readability)
[
[1，3] ，
[2，4]，
[2，4]，
[5，7]，
[6，8]，
[7，8]
]
...并假设我希望所有具有至少3个不同约会的范围，结果应为
...and assuming I want all ranges that have at least 3 different appointments occurring within them, the result should be
[
[2，3]，
[6，7]
]
为了使这一点不太抽象...
To make this a bit less abstract...
想象一下，我始终在工作人员的3个安装程序上运行24小时的窗口着色服务。我想在我的网站上显示所有可用的安装时间。因此，我需要隐藏已经安排了3个约会的任何时间范围。
Imagine I run a 24-hour window-tinting service with 3 installers on staff at all times. On my website, I want to show all available installation times. So I need to hide any time ranges where I've already got 3 appointments scheduled.
不一定要问任何人编写代码–但是是否有一种众所周知的算法
Not necessarily asking anyone to write code – but if there's a well-known algorithm for this class of problem that someone could point me to, I'd appreciate it.
谢谢。
[ EDIT]添加了javascript标记，因为我将在Node中实现它，但是答案不必在JS中。
added javascript tag because i'll be implementing this in Node, but answers don't need to be in JS.
我正在寻找一个非常通用的解决方案，因此，可以说约会可以在任何时间开始（不规范为小时或30分钟的时间段），并且可以是任何持续时间
I'm looking for a pretty general solution, so let's say that appointments can start at any time (not normalized to hour or 30 minute chunks) and can be of any duration
推荐答案
创建数组/对列表： {时间，标志= +1表示间隔的开始，-1表示间隔的结束}
按时间键排序列表。如果是平局账户的开始/结束标记（如果间隔为 [1,2] 和 [2,3] 不应相交）
Sort list by time key. In case of tie account for start/end flag (end before start if intervals like [1,2] and [2,3] should not intersect)
使 Counter = 0
遍历列表，每对添加一个标志到 Counter 。当 Counter 从 n-1 更改为 n 时-输出当计数器从 n 变为 n-1 -输出范围结束
Traverse list, for every pair add flag to Counter. When Counter changes from n-1 to n - output range begins, when Counter changes from n to n-1 - output range ends
这篇关于从一组约会中获取重叠时间范围的列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
