如何找到这些间隔具有一个共同的点的最大数目？ [英] How to find the maximal number of these intervals that have a common point?

问题描述

我一直在检讨算法，这是从Anany列维京的算法中书的问题..

I have been reviewing algorithms, this is question from Anany Levitin's algo book..

您有n个开区间列表（A1，B1），...，（一，BN）上的   实线。 （开区间（A，B）包括所有的点严格   其端点A和B之间，即（A，B）=（喜一＆LT; X - LT; B}）求   这些间隔具有一个共同的点的最大数目。对于   例如，对于时间间隔（1,4），（0,3），（-1.5，2），（3.6，5），这   最大数目是3。设计的算法针对此问题与   比二次时效性更好。

You have a list of n open intervals (a1, b1), ... , (an, bn) on the real line. (An open interval (a, b) comprises all the points strictly between its endpoints a and b, i.e., (a, b)= (xi a< x < b}.) Find the maximal number of these intervals that have a common point. For example, for the intervals (1, 4), (0, 3), ( -1.5, 2), (3.6, 5), this maximal number is 3. Design an algorithm for this problem with a better than quadratic time efficiency.

任何一个可以帮助我形成一个算法，或提出任何资源在互联网上。

Can any one help me forming an algorithm for it or suggest any resources on the internet..

谢谢， Hareendra

Thanks , Hareendra

推荐答案

接近，这将是如下的一种方法：假设你要排队的实数线的所有时段。从最左边开始，扫描整个间隔。输入的间隔每次递增活性间隔数的一个计数器，并在每次离开一次，递减计数器。在这个处理过程中的计数器的最大值是，那么你要寻找的数字。

One way to approach this would be as follows: suppose that you were to line up all the intervals on the real number line. Starting from the far left, scan across the intervals. Each time you enter an interval, increment a counter of the number of active intervals, and each time you leave one, decrement the counter. The maximum value of the counter over the course of this process is then the number you're looking for.

要实现这一点，排序所有时间间隔（一起）的起点和终点的进入长度为2n的一个巨大的列表，其中包含的所有段的开始和结束点，因为它们出现。然后，扫描列表从左到右更新基于该点找到计数器（1为起点，-1终点）。排序需要O（N log n）的时间和扫描需要O（n）的时间总共为O（n log n）的时间。

To implement this, sort all of the start and end points of the intervals (together) into a giant list of length 2n that contains the start and end points of all the segments as they appear. Then, scan the list from left to right updating the counter based on the points you find (+1 for start points, -1 for end points). Sorting takes O(n log n) time and the scan takes O(n) time for a total of O(n log n) time.

希望这有助于！

这篇关于如何找到这些间隔具有一个共同的点的最大数目？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！