如何找到这些具有公共点的区间的最大数量？

发布于 2024-12-28 16:29:51 字数 353 浏览 4 评论 0原文

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

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

谢谢，哈林德拉

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

一束光，穿透我孤独的魂 2025-01-04 16:29:51

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

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

希望这有帮助！

回复收藏 0 原文

漫雪独思 2025-01-04 16:29:51

排序为 Starts[] 和 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

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

回复收藏 0 原文

我做我的改变 2025-01-04 16:29:51

按开始时间对间隔进行排序。
创建按结束时间排序的优先级队列。
每次在向队列添加新间隔之前，轮询出所有与此不重叠的间隔。

队列大小将是一段时间内重叠的间隔。

私有间隔解决方案（Interval[]间隔）{
    Arrays.sort(间隔, (a, b)->{
       返回 a.start - b.start;
    });

    优先级队列<间隔> pq = new PriorityQueue<间隔>((a,b)->{
        返回a.end - b.end；
    });

    int 开始 = 0，结束 = 0；
    整数频率=0；
    for(间隔 i: 间隔){
        while(!pq.isEmpty() && i.start > pq.peek().end){
          pq.poll();
        }
        pq.offer(i);
        if(pq.size() > freq){
           频率 = pq.size();
           开始 = i.开始;
           结束 = pq.peek().end;
        }
    }
    返回新的间隔（开始，结束）；
}

Sort the intervals by their starting time.
Create a priority queue sorting by ending time.
Each time before adding a new interval to the queue, poll out all intervals has no overlap with this.

The queue size will be the overlapped intervals in a time.

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);
}

回复收藏 0 原文

~没有更多了~