Wie kann ich diesen Algorithmus verbessern, um die Laufzeit zu optimieren (finde Punkte in Segmenten)

Question

Ich habe 2 Integrale gegeben, die erste ist die Anzahl der Segmente (Xi, Xj) und die zweite ist die Anzahl der Punkte, die können oder können in diesen Segmenten sein.

Als Beispiel könnte der Eingang sein:

2 3 
0 5 
8 10 
1 6 11 

Wo, in erster Linie, 2 bedeutet "2 Segmente" und 3 bedeutet "3 Punkte". Die 2 Segmente sind "0 bis 5" und "8 bis 10", und die Punkte zu suchen sind 1, 6, 11. Der Ausgang

1 0 0 

Wo Punkt 1 in Segment „0 bis 5 ", und Punkt 6 und 11 sind in keinem Segment. Wenn ein Punkt in mehr als ein Segment angezeigt wird, wie ein 3 würde der Ausgang 2 seine

Der ursprüngliche Code, war nur eine Doppelschleife, die Punkte zwischen den Segmenten zu suchen. Ich benutzte den Java Arrays Quicksort (so modifiziert, wenn er Endpunkte von Segmenten sortiert, sortiert auch Startpunkte, also beginnen [i] und Ende [i] zum selben Segment i), um die Geschwindigkeit der Doppelschleife zu verbessern, aber es ist nicht genug.

Der nächste Code funktioniert gut, aber wenn zu viele Segmente gibt es wird es sehr langsam:

public class PointsAndSegments { 

    private static int[] fastCountSegments(int[] starts, int[] ends, int[] points) { 
     sort(starts, ends); 
     int[] cnt2 = CountSegments(starts,ends,points); 
     return cnt2; 
    } 

    private static void dualPivotQuicksort(int[] a, int[] b, int left,int right, int div) { 
    int len = right - left; 
    if (len < 27) { // insertion sort for tiny array 
     for (int i = left + 1; i <= right; i++) { 
      for (int j = i; j > left && b[j] < b[j - 1]; j--) { 
       swap(a, b, j, j - 1); 
      } 
     } 
     return; 
    } 
    int third = len/div; 
    // "medians" 
    int m1 = left + third; 
    int m2 = right - third; 
    if (m1 <= left) { 
     m1 = left + 1; 
    } 
    if (m2 >= right) { 
     m2 = right - 1; 
    } 
    if (a[m1] < a[m2]) { 
     swap(a, b, m1, left); 
     swap(a, b, m2, right); 
    } 
    else { 
     swap(a, b, m1, right); 
     swap(a, b, m2, left); 
    } 
    // pivots 
    int pivot1 = b[left]; 
    int pivot2 = b[right]; 
    // pointers 
    int less = left + 1; 
    int great = right - 1; 
    // sorting 
    for (int k = less; k <= great; k++) { 
     if (b[k] < pivot1) { 
      swap(a, b, k, less++); 
     } 
     else if (b[k] > pivot2) { 
      while (k < great && b[great] > pivot2) { 
       great--; 
      } 
      swap(a, b, k, great--); 
      if (b[k] < pivot1) { 
       swap(a, b, k, less++); 
      } 
     } 
    } 
    // swaps 
    int dist = great - less; 
    if (dist < 13) { 
     div++; 
    } 
    swap(a, b, less - 1, left); 
    swap(a, b, great + 1, right); 
    // subarrays 
    dualPivotQuicksort(a, b, left, less - 2, div); 
    dualPivotQuicksort(a, b, great + 2, right, div); 

    // equal elements 
    if (dist > len - 13 && pivot1 != pivot2) { 
     for (int k = less; k <= great; k++) { 
      if (b[k] == pivot1) { 
       swap(a, b, k, less++); 
      } 
      else if (b[k] == pivot2) { 
       swap(a, b, k, great--); 
       if (b[k] == pivot1) { 
        swap(a, b, k, less++); 
       } 
      } 
     } 
    } 
    // subarray 
    if (pivot1 < pivot2) { 
     dualPivotQuicksort(a, b, less, great, div); 
    } 
    } 

    public static void sort(int[] a, int[] b) { 
     sort(a, b, 0, b.length); 
    } 

    public static void sort(int[] a, int[] b, int fromIndex, int toIndex) { 
     rangeCheck(a.length, fromIndex, toIndex); 
     dualPivotQuicksort(a, b, fromIndex, toIndex - 1, 3); 
    } 

    private static void rangeCheck(int length, int fromIndex, int toIndex) { 
     if (fromIndex > toIndex) { 
      throw new IllegalArgumentException("fromIndex > toIndex"); 
     } 
     if (fromIndex < 0) { 
      throw new ArrayIndexOutOfBoundsException(fromIndex); 
     } 
     if (toIndex > length) { 
      throw new ArrayIndexOutOfBoundsException(toIndex); 
     } 
    } 

    private static void swap(int[] a, int[] b, int i, int j) { 
     int swap1 = a[i]; 
     int swap2 = b[i]; 
     a[i] = a[j]; 
     b[i] = b[j]; 
     a[j] = swap1; 
     b[j] = swap2; 
    } 

    private static int[] naiveCountSegments(int[] starts, int[] ends, int[] points) { 
     int[] cnt = new int[points.length]; 
     for (int i = 0; i < points.length; i++) { 
      for (int j = 0; j < starts.length; j++) { 
       if (starts[j] <= points[i] && points[i] <= ends[j]) { 
        cnt[i]++; 
       } 
      } 
     } 
     return cnt; 
    } 

    public static void main(String[] args) { 
     Scanner scanner = new Scanner(System.in); 
     int n, m; 
     n = scanner.nextInt(); 
     m = scanner.nextInt(); 
     int[] starts = new int[n]; 
     int[] ends = new int[n]; 
     int[] points = new int[m]; 
     for (int i = 0; i < n; i++) { 
      starts[i] = scanner.nextInt(); 
      ends[i] = scanner.nextInt(); 
     } 
     for (int i = 0; i < m; i++) { 
      points[i] = scanner.nextInt(); 
     } 
     //use fastCountSegments 
     int[] cnt = fastCountSegments(starts, ends, points); 
     for (int x : cnt) { 
      System.out.print(x + " "); 
     } 
    } 

Ich glaube, das Problem in dem CountSegments ist() -Methode, aber ich bin eine andere Art und Weise nicht sicher, ob es zu lösen . Angeblich sollte ich einen Divide and Conquer-Algorithmus verwenden, aber nach 4 Tagen bin ich bereit für jede Lösung. Ich fand a similar problem in CodeForces, aber die Ausgabe ist anders und die meisten Lösungen sind in C++. Da ich erst seit 3 ​​Monaten Java lerne, glaube ich, dass ich mein Wissenslimit erreicht habe.

Answer 1

bekommen Dies ist eine Implementierung ähnlich wie @ shole Idee:

public class SegmentsAlgorithm { 

    private PriorityQueue<int[]> remainSegments = new PriorityQueue<>((o0, o1) -> Integer.compare(o0[0], o1[0])); 
    private SegmentWeight[] arraySegments; 

    public void addSegment(int begin, int end) { 
     remainSegments.add(new int[]{begin, end}); 
    } 

    public void prepareArrayCache() { 
     List<SegmentWeight> preCalculate = new ArrayList<>(); 
     PriorityQueue<int[]> currentSegmentsByEnds = new PriorityQueue<>((o0, o1) -> Integer.compare(o0[1], o1[1])); 
     int begin = remainSegments.peek()[0]; 
     while (!remainSegments.isEmpty() && remainSegments.peek()[0] == begin) { 
      currentSegmentsByEnds.add(remainSegments.poll()); 
     } 
     preCalculate.add(new SegmentWeight(begin, currentSegmentsByEnds.size())); 
     int next; 
     while (!remainSegments.isEmpty()) { 
      if (currentSegmentsByEnds.isEmpty()) { 
       next = remainSegments.peek()[0]; 
      } else { 
       next = Math.min(currentSegmentsByEnds.peek()[1], remainSegments.peek()[0]); 
      } 
      while (!currentSegmentsByEnds.isEmpty() && currentSegmentsByEnds.peek()[1] == next) { 
       currentSegmentsByEnds.poll(); 
      } 
      while (!remainSegments.isEmpty() && remainSegments.peek()[0] == next) { 
       currentSegmentsByEnds.add(remainSegments.poll()); 
      } 
      preCalculate.add(new SegmentWeight(next, currentSegmentsByEnds.size())); 
     } 
     while (!currentSegmentsByEnds.isEmpty()) { 
      next = currentSegmentsByEnds.peek()[1]; 
      while (!currentSegmentsByEnds.isEmpty() && currentSegmentsByEnds.peek()[1] == next) { 
       currentSegmentsByEnds.poll(); 
      } 
      preCalculate.add(new SegmentWeight(next, currentSegmentsByEnds.size())); 
     } 
     SegmentWeight[] arraySearch = new SegmentWeight[preCalculate.size()]; 
     int i = 0; 
     for (SegmentWeight l : preCalculate) { 
      arraySearch[i++] = l; 
     } 
     this.arraySegments = arraySearch; 
    } 

    public int searchPoint(int p) { 
     int result = 0; 
     if (arraySegments != null && arraySegments.length > 0 && arraySegments[0].begin <= p) { 
      int index = Arrays.binarySearch(arraySegments, new SegmentWeight(p, 0), (o0, o1) -> Integer.compare(o0.begin, o1.begin)); 
      if (index < 0){ // Bug fixed 
       index = - 2 - index; 
      } 
      if (index >= 0 && index < arraySegments.length) { // Protection added 
       result = arraySegments[index].weight; 
      } 
     } 
     return result; 
    } 

    public static void main(String[] args) { 
     SegmentsAlgorithm algorithm = new SegmentsAlgorithm(); 
     int[][] segments = {{0, 5},{3, 10},{8, 9},{14, 20},{12, 28}}; 
     for (int[] segment : segments) { 
      algorithm.addSegment(segment[0], segment[1]); 
     } 
     algorithm.prepareArrayCache(); 

     int[] points = {-1, 2, 4, 6, 11, 28}; 

     for (int point: points) { 
      System.out.println(point + ": " + algorithm.searchPoint(point)); 
     } 
    } 

    public static class SegmentWeight { 

     int begin; 
     int weight; 

     public SegmentWeight(int begin, int weight) { 
      this.begin = begin; 
      this.weight = weight; 
     } 
    } 
} 

Er druckt:

-1: 0 
2: 1 
4: 2 
6: 1 
11: 2 
28: 0 

EDITED:

public static void main(String[] args) { 
    SegmentsAlgorithm algorithm = new SegmentsAlgorithm(); 
    Scanner scanner = new Scanner(System.in); 
    int n = scanner.nextInt(); 
    int m = scanner.nextInt(); 
    for (int i = 0; i < n; i++) { 
     algorithm.addSegment(scanner.nextInt(), scanner.nextInt()); 
    } 
    algorithm.prepareArrayCache(); 
    for (int i = 0; i < m; i++) { 
     System.out.print(algorithm.searchPoint(scanner.nextInt())+ " "); 
    } 
    System.out.println(); 
} 

Answer 2

die Constraints von OP Gegeben sei n die Anzahl der Segmente, m die Anzahl der Punkte sein Abfrage zu sein, wo n,m < = 5 * 10^4, ich mit einer O(nlg(n) + mlg(n)) Lösung kommen kann (was sein sollte genug, um die meisten Online-Richter passieren)

Da jede Abfrage eine Überprüfung Problem ist: kann der Punkt von einigen Intervallen abgedeckt werden, ja oder nein, wir brauchen nicht zu finden, was/wie viele Intervalle der Punkt hat wurde abgedeckt.

Umriss des Algorithmus:

1. sortieren alle Intervalle ersten Punkt beginnen, wenn tie dann durch Länge (ganz rechts Punkt enden)
2. Versuchen Sie, die Intervalle zu verschmelzen einige disjoint überlappende Intervalle zu erhalten. Für z.B. (0,5), (2,9), (3,7), (3,5), (12,15) erhalten Sie (0,9), (12,15). Da die Intervalle sortiert sind, kann dies gierig in O(n)
3. durchgeführt werden. Oben sind die Vorberechnung, jetzt für jeden Punkt, die wir mit den disjunkten Intervallen abfragen.Einfach binäre Suche, wenn eine Intervall solchen Punkt enthält, jede Abfrage O(lg(n)) ist und wir haben m Punkte, so total O(m lg(n))

ganzen Algorithmus kombiniert, werden wir einen O(nlg(n) + mlg(n)) Algorithmus