重叠间隔和重叠量 [英] Overlapping intervals and the amount of overlaps
问题描述
该问题可能与其他问题相似，但有所不同。假设我们有一组这样的间隔，比如说A-9是数字，但是为了格式化，我使用了字母）：
This question might be similar to others but is a bit different. Let's say we have a set of intervals that goes like this let's say A-9 are numbers but for the sake of formatting I used letters):
<-a---> <------c--->
<------------MAIN>
ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789
<--d-> <--b------->
所以我们有一个主区间，从 I 到 Z ，区间 a 从 M 到 S ，依此类推。
So we have the Main interval which goes from I to Z, the interval a that goes from M to S and so on.
现在，我想在其中具有最重叠的区间主要参数（本质上是基本约束），将是MO（具有（a和d）和QS（a和b）以及UZ（b和c）），每个都有2个重叠（ Z以外的所有值是不可能的，因为它在主区间之外
Now I want to have the intervals where I have the most overlaps WITHIN the main one (which is essentially the basic constraint) that would be M-O with (a and d) and Q-S (a and b) and U-Z (b and c) with 2 overlaps each (everything beyond Z is out of the question because it is outside the main interval
我本质上是想要区间的列表（又称数组）以及内部的重叠数Main，而在PHP中没有将Main计入该数字（不需要排序，有足够的方法可以做到这一点）。
I essentially want a list (aka array) of the intervals and the number of overlaps inside the Main, while not counting the main into that number (sorting not needed there are enough ways to do this) in PHP.
我想到了对间隔进行图像处理然后计算每个像素列的颜色
I thought of making a picture of the intervals and then counting the colors for each pixel column but that's
- 平均问题
- 效率低
- 可能很慢
因此，TLDR，我需要一个解决方案
so, TLDR, I need a solution that
- 在PHP中工作
- 相对相对快速
- 是可靠的
- 为您提供帮助重叠间隔及其重叠计数
- 有一个主要间隔用作基本约束，不计入重叠。
- works in PHP
- is relatively fast
- is reliable
- gives you the overlapping intervals with their overlap count
- has a main interval used as base constraint which is not counted to the overlap.
我知道这是一个非常具体的问题，但我并不精通数学和算法。
I know it's a very specific question but I am not that well versed in Math and algorithms.
推荐答案
此算法的基本算法是遍历整个长度，计数器在遇到起点时增加，而在遇到终点时减少。
The basic algorithm for this is go over the whole length with a counter that increases when you meet a start point and decreases when you meet an end point.
保持跟踪
再次遍历整个长度，这次将位置添加到您的 result 数组中时间：
1.您在MAIN零件边界之内。
2.您的计数器（保持不变）等于您之前计算的最大值。
Go over the whole length again, this time add locations to your result array when:
1. You are within the MAIN part borders.
2. Your counter (which is maintained the same way) is equal to the maximum you calculated before.
这篇关于重叠间隔和重叠量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
