4

我一直在审查算法，这是来自 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。针对这个问题设计一个算法，该算法具有优于二次时间效率。

任何人都可以帮我形成一个算法或建议互联网上的任何资源..

谢谢，哈伦德拉

4

3 回答 3

5

解决此问题的一种方法如下：假设您要在实数线上排列所有间隔。从最左边开始，扫描间隔。每次输入间隔时，将活动间隔数的计数器递增，每次离开时，将计数器递减。在此过程中，计数器的最大值就是您要查找的数字。

为了实现这一点，将所有区间的起点和终点（一起）排序到一个长度为 2n 的巨大列表中，其中包含所有出现的段的起点和终点。然后，从左到右扫描列表，根据您找到的点更新计数器（+1 表示起点，-1 表示终点）。排序需要 O(n log n) 时间，扫描需要 O(n) 时间，总共需要 O(n log n) 时间。

希望这可以帮助！

于 2012-01-23T10:03:19.393 回答
2

Sort into Starts[] and Ends[].

i = 0; j = 0; max = 0; total = 0;

while ( i < n ) {
  if ( Starts[i] < Ends[j] ) {
    i++;
    total++;
    if ( total > max ) max = total;
  } else if ( Ends[j] < Starts[i] ) {
    j++;
    total--;
  } else {
    i++;
    j++;
  }
} // while
于 2012-01-23T10:16:13.403 回答
0
  1. 按开始时间对间隔进行排序。
  2. 创建按结束时间排序的优先级队列。
  3. 每次在队列中添加一个新的间隔之前，轮询出所有与此没有重叠的间隔。

  4. 队列大小将是一次重叠的间隔。

    private Interval solution(Interval[] intervals) {
    Arrays.sort(intervals, (a, b)->{
       return a.start - b.start;
    });

    PriorityQueue<Interval> pq = new PriorityQueue<Interval>((a,b)->{
        return a.end - b.end;
    });

    int start = 0, end = 0;
    int freq = 0;
    for(Interval i: intervals){
        while(!pq.isEmpty() && i.start > pq.peek().end){
          pq.poll();
        }
        pq.offer(i);
        if(pq.size() > freq){
           freq = pq.size();
           start = i.start;
           end = pq.peek().end;
        }
    }
    return new Interval(start, end);
}
于 2017-11-07T07:13:58.737 回答