我在其他地方找到了类似的问题,但没有考虑过优先级。
R : (------------|xxxxxxx|ooo|xx|----------------) (---)
S1: (------------) (----------------) (---)
S2: (xxxxxxxxxxxxxxx) (xxxxxx)
S3: (ooooooo) (oo)
假设我有三个日期范围的来源,名称分别为S1、S2和S3,优先级分别为1、2和3(1为最高),并且有一个结果R。我需要得到不重叠的日期范围,其中最高优先级具有优先权。
我想到了一个解决方案,但它是相当顺序的。首先,我创建一个按升序日期、降序优先级排序的表(在日期冲突的情况下,表中最高优先级优先),并标记其ID和操作(打开或关闭范围)。
ID | Action | Priority | Date |
--------------------------------
S1a | Open | 1 | 1 |
S2a | Open | 2 | 2 |
S1a | Close | 1 | 3 |
S3a | Open | 3 | 4 |
S2a | Close | 2 | 5 |
S2b | Open | 2 | 6 |
S3a | Close | 3 | 7 |
S1b | Open | 1 | 8 |
S2b | Close | 2 | 9 |
S3b | Open | 3 | 10 |
S3b | Close | 3 | 11 |
S1b | Close | 1 | 12 |
S1c...
然后我开始迭代这个表格,并填充一个有序列表和结果表格:
因此,第一行将是:
Order List: Result:
ID | Priority | ID | Action | Date |
S1a| 1 | S1a| Open | 1 |
第二行,添加了S2a的开放日期,但由于表格中存在更高的优先级,因此不写任何内容:
Order List: Result:
ID | Priority | ID | Action | Date |
S1a| 1 | S1a| Open | 1 |
S2a| 2 |
第三行,关闭S1a,写下结束日期,并且由于S2a移动到列表顶部,也要为S2a写下开放日期。
Order List: Result:
ID | Priority | ID | Action | Date |
x S1a| 1 | S1a| Open | 1 |
S2a| 2 | S1a| Close | 3 |
S2a| Open | 3 |
我猜你能看出这要往哪个方向发展……需要做很多交叉检查等操作,但在纸上看起来似乎可行。如果有人需要的话,我可以更好地解释一下算法,但我认为它不难跟踪。如果有更高优先级的有序列表,则不会写入任何内容。当删除较高优先级时,下一个最大值重新打开。
也许有更好、更具体的想法吗?谢谢你的时间!