topic description

enter a list of intervals represented by tuples of two elements. Find out the interval with the least number of overlaps.
example: enter [(1.1,10.1), (2.1) 10.1), (3.110.1], because (1.1,2.1) repeats once, (2.1,3.1) repeats twice, (3.110.1) repeats 3 times, so the interval with the least number of overlaps is (1.1,2.1).

sources of topics and their own ideas

A statistical topic.
my idea:

1. sorts all entered digits in descending order. (preprocessing)
2. create a mapping f_int between 0mern and all input digits. To facilitate the simultaneous creation of a mapping int_f for all input numbers to 0murn.
3. create a histogram histogram (essentially python list), size is 2*len (f_int)-1. Why? I need to represent the interval with elements where index is odd. Elements with an even number of index are used to represent the two ends of each interval.
4. iterates through all the inputs, and based on each input, the element + 1 of the corresponding index in the histogram indicates the number of overrides + 1.
5. create a histogram aim, to put the odd items of histogram
6. finds the smallest element in the aim and its corresponding index, and then finds the two elements adjacent to the index in the histogram, which is the target interval.

this basic verification is feasible.

related codes

/ / Please paste the code text below (do not replace the code with pictures)

def find_least_overlap(intervals):
    -sharp 1
    all_nums = sorted([p for interval in intervals for p in interval])
    -sharp 2
    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
    -sharp 3
    histogram = [0 for i in range(2*i-1)]

    -sharp 4
    for interval in intervals:
        for _ in range(2*f_int[interval[0]], 2*f_int[interval[1]]+1):
            histogram[_] += 1
    -sharp 5
    aim = [histogram[i] for i in range(len(histogram)-1) if i % 2 == 1]
    -sharp 6
    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]

what result do you expect? What is the error message actually seen?

this algorithm runs faster when the all_nums is small and each input interval is small. When the all_nums becomes larger, the interval span of the input becomes larger, and it becomes slower. Because you need to do a lot of + 1 operations in step 3.
I hope you can think about it together and see if you can get a better way.

has a related question, and the answer gives a way to find out the number of occurrences of each element (all int). I checked the speed of the toilet and found that it was not ideal.
https://codeshelper.com/q/10.