有多个时间段,格式是hh:mm,如何判断这多个时间段是否涵盖了一整天的所有时间?

有多个小时分钟格式的时间段,例如06:00 - 12:00、13:30 - 19:00、19:00 - 22:30、、全天的时间以半小时划分,也就是半个小时一档,要求判断输入的一个或多个时间段的合集是否涵盖了全天所有的时间,不是单纯的时间段时间相加够24小时。

1. 定义一个长度为48的布尔数组,记录48个区间的涵盖状态,初始值默认全为false。

2. 定义一个涵盖状态更新方法,传入一个数组,一个起始下标,一个结束下标。方法体为:将数组从起始下标到结束下标(不包含自身,起始和结束相等时不进行操作)间的元素值设为true。

3. 循环读取时间段,将时间段转换为数组下标。调用状态更新方法更新涵盖状态数组

4. 遍历涵盖状态数组,全为true则表示涵盖了一整天的所有时间,否则有缺失。

PS:整体思路参考位图BitMap。

把时间区间映射到[0, 48] 区间,例如 [00:30, 1:30] 映射到 [1,3],这个作为一个 Range。

 

然后写一个 RangeList 类,提供一个接口 RangeList.insert(Range r); 内部维持一个 List<Range> 但是会做自动合并,例如插入的 Range 和已有的 Range 集合中的多个有交集,那么这几个 Range 会合并成一个大Range,替换掉原来的多个 Range。这样,最后只要看是否只剩下一个 [0,48] 元素就知道是否覆盖全天时间。

 

其中,插入算法,可以用上二分查找算法。一直维持 Range 集合的自然排序,每次插入时通过二分查找找到有交集的第一个区间和最后一个区间,再合并。