Merge multiple intervals by splitting

Question

There're two arrays: regular_events and special_events. Each of them contains multiple arrays, which present as [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]] 

I want to implemnt a function SplitMerge to merge these events.

There're some rules for merging:

1. If there's no overlapping events, it will be merged.
2. If special_events is overlapping regular_events, the special_events will be keep, and regular_events will be increased or splitted.
3. special_events are not overlapping with each other.
4. regular_events are not overlapping with each other.
5. regular_events and special_events are sorted by start_time

For some example:

1. Non overlapping:
   • Input: regular_events = [[5,10]], special_events = [[0,3],[11,15]]
   • Output: [[0,3],[5,10],[11,15]]
   • Explanation: The special_events and regular_events are not overlapping with each other, merge them as result.
2. Partially overlapping:
   • Input: regular_events = [[5,10]], special_events = [[3,7],[9,12]]
   • Output: [[3,7],[7,9],[9,12]]
   • Explanation: The special_events[0] and special_events[1] is partially overlapping with regular_events[0], decrease the regular_events[0] to [7,9] as result
3. Fully overlapping:
   • Input: regular_events = [[5,10]], special_events = [[7,8]]
   • Output: [[5,7],[7,8],[8,10]
   • Explanation: The special_events[0] is fully overlapping on regular_events[0], it split regular_events to [[5,7],[8,10]] and merge [[7,8]] as result.
4. Cross overlapping:
   • Input: regular_events = [[5,10], [12,15]], special_events = [[8,14]]
   • Output: [[5,8],[8,14],[14,15]]
   • Explanation: The special_events[0] is partially overlapping both regular_events[0] and regular_events[1], it decrease regular_events and merge as result.

I've tried solve it by slice (in Go) and Linked List (in Python), but not in use.

I also asked GitHub Copilot Chat, it gaves the answer:

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

But it didn't work in case 2: Partially overlapping.

Answer 1

Consider the next implementation

evs holds sorted time points with event type

state remembers active events

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) and (ev[0] > last_reg):
                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))