通过拆分合并多个区间

Question

有两个数组：

regular_events

和

special_events

。每个都包含多个数组，表示为

[start_time, end_time]

// Only one event, starts from 5:00 to 10:00
regular_events = [[5, 10]] 

// First event starts from 0:00 to 3:00, and second event starts from 12:00 to 15:00
special_events = [[0, 3], [12, 15]] 

我想实现一个函数

SplitMerge

来合并这些事件。

合并有一些规则：

1. 如果没有重叠的事件，则会合并。
2. 如果

   special_events

   与

   regular_events

   重叠，则

   special_events

   将保留，而

   regular_events

   将增加或分裂。

3. special_events

   彼此不重叠。

4. regular_events

   彼此不重叠。

5. regular_events

   和

   special_events

   按

   start_time

排序

举个例子：

1. 不重叠：
   • 输入：

     regular_events = [[5,10]]

     、

     special_events = [[0,3],[11,15]]

   • 输出：

     [[0,3],[5,10],[11,15]]

   • 说明：

     special_events

     和

     regular_events

     彼此不重叠，将它们合并为结果。
2. 部分重叠：
   • 输入：

     regular_events = [[5,10]]

     、

     special_events = [[3,7],[9,12]]

   • 输出：

     [[3,7],[7,9],[9,12]]

   • 说明：

     special_events[0]

     和

     special_events[1]

     与

     regular_events[0]

     部分重叠，将

     regular_events[0]

     减少为

     [7,9]

     ，结果
3. 完全重叠：
   • 输入：

     regular_events = [[5,10]]

     、

     special_events = [[7,8]]

   • 输出：

     [[5,7],[7,8],[8,10]

   • 解释：

     special_events[0]

     与

     regular_events[0]

     完全重叠，它将

     regular_events

     拆分为

     [[5,7],[8,10]]

     并合并

     [[7,8]]

     。
4. 交叉重叠：
   • 输入：

     regular_events = [[5,10], [12,15]]

     、

     special_events = [[8,14]]

   • 输出：

     [[5,8],[8,14],[14,15]]

   • 解释：

     special_events[0]

     与

     regular_events[0]

     和

     regular_events[1]

     部分重叠，它减少

     regular_events

     并合并。

我尝试过通过切片（在 Go 中）和链表（在 Python 中）来解决它，但没有使用。

我也问过 GitHub Copilot Chat，它给出了答案：

def SplitMerge(events, special_events):
    merged = []
    i, j = 0, 0
    while i < len(events) and j < len(special_events):
        if events[i][1] <= special_events[j][0]:
            merged.append(events[i])
            i += 1
        elif events[i][0] >= special_events[j][1]:
            merged.append(special_events[j])
            j += 1
        else:
            if events[i][0] < special_events[j][0]:
                merged.append([events[i][0], special_events[j][0]])
            if events[i][1] > special_events[j][1]:
                merged.append([special_events[j][1], events[i][1]])
            i += 1
    while i < len(events):
        merged.append(events[i])
        i += 1
    while j < len(special_events):
        merged.append(special_events[j])
        j += 1
    return merged

但是在情况2：部分重叠的情况下它不起作用。

Answer 1

考虑下一步实施

evs

保存按事件类型排序的时间点

state

记住活动事件

def SplitMerge(events, special_events):
    evs = []
    for e in events:
        evs.append((e[0], 2))
        evs.append((e[1], 0))
    for s in special_events:
        evs.append((s[0], 3))
        evs.append((s[1], 1))
    evs.sort()
    print(evs)
    merged = []
    state = 0
    for ev in evs:

        if ev[1] == 2:    #regular start
            last_reg = ev[0]
            state |= 2

        elif ev[1] == 3:   #special start
            if state == 2:
                merged.append([last_reg, ev[0]])
            last_spec = ev[0]
            state |= 1

        elif ev[1] == 0:    #regular end
            if state == 2:
                merged.append([last_reg, ev[0]])
            state &= 1       #clear regular bit

        else: #1     #special end
            merged.append([last_spec, ev[0]])
            if (state & 2):
                last_reg = ev[0]
            state &= 2      #clear special bit
    return merged

regular_events = [[5,10]]
special_events = [[0,3],[11,15]]

regular_events = [[5,10]]
special_events = [[3,7],[9,12]]

#regular_events = [[5,10]]
#special_events = [[7,8]]

#regular_events = [[5,10], [12,15]]
#special_events = [[8,14]]

print(SplitMerge(regular_events, special_events))