data-structures - 设计合并 session 日程的数据结构

Question

我被要求为 session 日程设计一个数据结构，然后将它们合并。例如，如果人员 A 的 session 时间为上午 9:00 到上午 10:00，人员 B 的 session 时间为上午 9:30 到上午 11:30，则合并的繁忙时段为上午 9:00 到上午 11:30。

我为 Person 创建了类，该类包含 session 对象的集合。 Meeting 类的开始时间 [hh:mm] 采用 24 小时格式，以便我可以轻松进行比较。

class Person {
String name;
Collection<Meeting> meetings;

}


class Meeting{
int hh, mm;
int duration; // duration will be in minutes from where we can get the end time. 
}

我想知道哪种数据结构对于合并来说最有效。 一种方法是使用 session 排序的ArrayList。

如有更好的设计，我们将不胜感激。

Answer 1

正如 @Anonymouse 建议的那样，您可以使用 96 位(即 12 个字节)来表示一天，因此从凌晨 1:00 开始的 30 分钟 session 将表示为 110000，您可以使用简单的 |对所有数字进行操作。

时间 O(n) 内存 O(12n) 字节。理论上会快得多。

<小时/>

给定一个 session [开始时间(以分钟为单位)，结束时间(以分钟为单位)]。

重叠时将两个 session (Sa 和 Sb)合并到 Sc

Sc [最小值(SA-start、SB-start)、最大值(SA-end、SB-end)] 并将合并的 session 存储在集合中。如果不重叠，则可以单独存储它们。

我们知道一天的总分钟数 = 24 * 60 = 1440 如果你有 15 分钟单位，那么它就变成 24 * 60/15 = 96 (低于 1 字节)

因此每个计划需要 2 个字节，即字节开始、结束。

时间 O(n) 内存 O(2n) 字节

<小时/>

如果您稍后必须删除 session ，这两种方法都不起作用。为此，您肯定会单独举行所有原始 session 日程。