har*_*ddy 4 algorithm intersection line segment computational-geometry
我一直在审查算法，这是Anany Levitin的算法书中的问题。
您在实线上有n个打开间隔（a1，b1），...，（an，bn）的列表。（一个开放区间（a，b）严格包含其端点a和b之间的所有点，即（a，b）=（xi a <x <b}。）找出这些区间中具有共同点的最大数目例如，对于时间间隔（1、4），（0、3），（-1.5、2），（3.6、5），此最大数为3。为此问题设计一种算法，其算法优于二次方程时间效率。
任何人都可以帮助我为它形成算法或在互联网上建议任何资源。
谢谢，哈琳德拉
解决此问题的一种方法如下：假设您要在实数行上排列所有间隔。从最左端开始，扫描间隔。每次输入间隔时，请增加一个有效间隔数的计数器，每次离开时，请减少计数器。在此过程中，计数器的最大值就是您要查找的数字。
要实现这一点，请将间隔的所有起点和终点（一起）排序到一个长度为2n的巨型列表中，该列表包含所有分段出现时的起点和终点。然后，从左到右扫描列表，根据找到的点更新计数器（+1代表起点，-1代表终点）。排序花费O（n log n）时间，而扫描花费O（n）时间，总共O（n log n）时间。
希望这可以帮助！