Find max nested elements that can be retrieved, given a max sliding range

ZooPanda 0
Viewed 28

Given multiple array of array of elements T_n,

T_0 = [[0,2], [1,8], [5,9], [2,4], [7,8], [10,10]] 
T_1 = [[7,10], [11,13], [20,25]]

where the first index of each element array indicates the start "time" and the second index the "end" time of each entity, for example [0,2] means start = 0, end = 2. (start and end time can be the same as well, in which case, its a "free" entity. Entity refers to an array in the array of arrays)

and a max "stay time"

M = 2

Example:

Given just one T,

T_0 = [[0,2], [1,8], [5,9], [2,4], [7,8], [10,10]] 

M = 2

The max number of entities will be 4, since I can "stay" from start = 0 to end = 2, so I will attain the entities [0,2], [1,8], [2,4], on top of the free entity [10,10]. Since there is only 1 T, the T_n that gives me the max entities will simply be T_0

Another Example

Given two Ts,

T_0 = [[0,2], [2,4]]
T_1 = [[7,10], [11,13], [20,25]]

M = 2

I can get 2 entities from T_0 by "staying" from start = 1 and end = 3. I can also get 2 entities from T_1 by "staying from start = 9 and end = 11. So, the max entities i can get is 2. And the T that will give me the max number of entities is both T_0 and T_1, since they give the same number of entities.

So the question is: How do I find an algorithm that gives me the maximum number of entities I can attain, and which T_n will give me this max number of entities?

I have tried something like a sliding window method, but I don't think it is the most efficient way, and was wondering if there is another way of doing it.

algorithm python
1 Answers

This algorithm should give the max number of attained events in O(n logn) for each individual array. Apply that to each array and then pick the best one.

  • first, remove all the "free" events from the array and store their number in a separate variable
  • use two heaps to keep track of remaining events sorted by starting time, and active events (just the end time)
  • since an event counts as attained if it is just "touched" by the time window, test all times in order such that the window's starting time is the ending time of any event, or vice versa
  • for each starting time, move events from the remaining heap to the active heap according to their start time, and remove them from the active heap according to their end time
  • get the best such window and add the previously determined number of free events

Since you only have to test windows coinciding with the start/end time of the n events, and the most complex step are the heap operations with O(logn) being applied to each event at most once, overall complexity should be O(n logn).

import heapq

def best_window(arr, m):
    free = sum(1 for a, b in arr if a == b)
    cand_times = sorted([a-m for a, b in arr] + [b for a, b in arr])
    remaining = sorted((a, b) for a, b in arr if a != b)
    active = []
    attained = {}
    for t in cand_times:
        while remaining and t + m >= remaining[0][0]:
            a, b = heapq.heappop(remaining)
            heapq.heappush(active, b)
        while active and t > active[0]:
            heapq.heappop(active)
        attained[t] = len(active)
    best = max(attained, key=attained.get)
    return attained[best] + free, best
tobias_k0
Related