1

Example: panda dataframe is,

   start end
0. 10    20
1. 30    40
2. 50    60
3. 25    35
4. 70    80

need to create a list,

ovrlap = [false, true, false, true, false]

as idx 1 and 3 are overlapping so in the list also in those 2 idx are true.

  • I tried with 2 for loops, but that's taking a long time. Looking for a fast algo.

  • It's not like merging overlaps, as that doesn't maintain the order of the original list, sorts the list.

imankalyan
  • 155
  • 1
  • 8
  • Does this answer your question? [Merging Overlapping Intervals](https://stackoverflow.com/questions/43600878/merging-overlapping-intervals) – Shamis Feb 25 '21 at 11:59
  • You are asking for an overlap detection, which is almost the same as [merging the overlaps.](https://stackoverflow.com/questions/44660111/algorithm-for-merging-overlapping-intervals) The only difference is that instead of merging, you will be only marking them. – Shamis Feb 25 '21 at 12:01

1 Answers1

0

I'm using this code:

def overlapDetect(arr):
    res = [False for i in range(len(arr))]
    arr_srt = sorted(arr, key=lambda l:l[0])
    for i in range(len(arr_srt) - 1):
        cur_s, cur_e = arr_srt[i]
        nxt_s, nxt_e = arr_srt[i+1]
        if nxt_s <= cur_e <= nxt_e:
            cur_idx = arr.index(arr_srt[i])
            nxt_idx = arr.index(arr_srt[i+1])
            res[cur_idx] = res[nxt_idx] = True
    return res

arr = [[10, 20], [30, 40], [50, 60], [25, 35]]
print(overlapDetect(arr))

But that's taking a long time, 10 mints for arr length of 100,000.

Looking for a better solution.

imankalyan
  • 155
  • 1
  • 8