I'm having a hard time coming up with an algorithm at work that essentially computes the following
Suppose you two arrays. Each element in the array contains price and time. Each array is sorted in ascending order of time. e.g., array1 = [(10, 1), (5, 2), (7, 4)] means that price = 10 from time = 1 to 2, price = 5 from time = 2 to 4 and price = 7 at time = 4. Compute the total overlap time of the 2 arrays in which the absolute price difference is <= 10.
So just to give an example, suppose we have
array1 = [(10, 1), (5, 2), (7, 4)]
array2 = [(19, 0), (6, 2), (23, 4)]
The overlap time here is 3. From time = 1 to time = 4 (non-inclusive), the difference is <= 10. For the time interval [0, 1), the price difference is undefined and does not contribute to the overlap time. For the interval [1, 2), the price difference is < 10 and ditto for [2, 4). So they have a price diff < 10 for the interval [1, 4), hence the answer is 3.
(It's a lot easier to visualize if you plot it on a x-y plot and see when the 2 lines have a difference in y of <= 10 for the same x value).
I've tried several algorithms of looping through the intervals, but always manage to miss some edge cases. Admittedly, I'm not good at these kind of interval merging problems (I think there's a specific word that describes this class of problems but I can't recall it). What are some foolproof ways to solve this?
I feel like there's a particular way I should be thinking of this problem that would make the implementation trivial, and evidently I'm not thinking about it that way.
The idea is to visit the entries from the two input arrays in sorted order (by their time): whenever you can select from either array, choose the item with the least time, and move to the next item in that selected array, so in the next iteration that item can be compared by its time.
Once you have implemented that traversal, you can traverse items until you have a price from both sources, and compare the differences as the traversal continues.
Here is an implementation in Python:
# Merge two sorted price-evolution lists in sorted order
def merged(list1, list2):
iters = (iter(list1), iter(list2))
val = [next(iters[0], None), next(iters[1], None)]
while val[0] is not None or val[1] is not None:
i = val[0] is None or val[1] is not None and val[0][1] > val[1][1]
yield i, val[i]
val[i] = next(iters[i], None)
def overlap_time(list1, list2, maxdiff):
prices = {} # To keep track of last price per source-list
result = 0
# Iterate the price change events in chronological order
for source, (price, time) in merged(list1, list2):
# Do we have prices from both source lists and are they close?
if len(prices) == 2 and abs(prices[0] - prices[1]) <= maxdiff:
result += time - prevtime
prices[source] = price
prevtime = time
return result
Example call:
list1 = [(10, 1), (5, 2), (7, 4)]
list2 = [(19, 0), (6, 2), (8, 4), (28, 8)]
print(overlap_time(list1, list2, 10)) # 3