Как найти максимальное количество этих интервалов, имеющих общую точку?

Question

Я рассматривал алгоритмы, это вопрос из книги-анго Анани Левитина ..

У вас есть список из n открытых интервалов (a1, b1), ..., (an, bn) на реальная линия. (Открытый интервал (a, b) охватывает все точки строго между его конечными точками a и b, то есть (a, b) = (xi a

Может ли кто-нибудь помочь мне составить алгоритм для него или предложить какие-либо ресурсы в Интернете ...

Спасибо, Hareendra

Answer 1

Один из подходов к этому заключается в следующем: предположим, что вы должны выстроить все интервалы в строке действительных чисел.Начиная с крайнего левого, сканируйте через интервалы.Каждый раз, когда вы вводите интервал, увеличивайте счетчик количества активных интервалов, а каждый раз, когда вы его оставляете, уменьшаете счетчик.Максимальное значение счетчика в течение этого процесса - это число, которое вы ищете.

Чтобы реализовать это, отсортируйте все начальную и конечную точки интервалов (вместе) в гигантский список.длиной 2n, которая содержит начальную и конечную точки всех сегментов по мере их появления.Затем отсканируйте список слева направо, обновляя счетчик, основываясь на найденных вами точках (+1 для начальных точек, -1 для конечных точек).Сортировка занимает O (n log n) времени, а сканирование занимает O (n) времени в общей сложности O (n log n).

Надеюсь, это поможет!

Answer 2

Сортировка по Началам [] и Концам [].

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

Answer 3

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