CODEWITHSUNDEEP
algorithm
Eric Tu
Eric Tu

Reputation: 21

The interval with the smallest number of overlaps

I have a series of intervals.I want to find the interval with the smallest number of overlaps.

For example:
input:

[(1.1, 10.1), (2.1,10.1), (3.1, 10.1)]

because (1.1, 2.1) overlap 1 time, (2.1, 3,1) overlap 2 times, (3.1, 10.1) overlap 3 times. return (1.1, 2.1)

My solution：

1.create a dict(name f_int) to save all number in input.{0:1.1, 1.2.1, 2:3.1 ...}

2.create a list name histogram of length 2*len(f_int)-1, all items are 0.odd index mean "interval" of its two adjacent elements.

3.Traversal input，all items between f_int[each.start] and f_int[each.end] += 1

4.find min in items in histogram with odd index，its two adjacent elements is the result

it works， but when f_int is large,it is slow(spend much time in 3)

def find_least_overlap(intervals):
    all_nums = sorted([p for interval in intervals for p in interval])

    # 1
    f_int = {}
    int_f = {}
    i = 0
    for n in all_nums:
        try:
            f_int[n]
        except:
            f_int[n] = i
            int_f[i] = n
            i += 1
    # 2
    histogram = [0 for i in range(2*i-1)]

    # 3
    for interval in intervals:
        for _ in range(2*f_int[interval[0]], 2*f_int[interval[1]]+1):
            histogram[_] += 1
    # 4
    aim = [histogram[i] for i in range(len(histogram)-1) if i % 2 == 1]
    min_overlap = aim.index(min(aim)) * 2 + 1
    pre_item = (min_overlap - 1) / 2
    next_item = (min_overlap + 1) / 2
    return int_f[pre_item], int_f[next_item]

Upvotes: 1

Views: 233

Answers (1)

MBo
MBo

Reputation: 80177

Create list of pairs (time, flag = +-1 for start or end of interval)

Sort list by time.
In case of tie consider also start/end flag (end before start if intervals like [1,4] and [4,7] should not intersect giving zero-length intersection range)

Make overlapping = 0

Traverse list, for every pair add flag to overlapping

When overlapping changes - output range ends, new one starts

Compare overlapping with current minimal value (excluding starting 0)

Upvotes: 1

Related Questions