How can improve this algorithm to optimize the running time (find points in segments)

Question

I'm given 2 integrals, the first is the number of segments (Xi,Xj) and the second is the number of points that can or cant be inside those segments.

As an example, the input could be:

2 3
0 5
8 10
1 6 11

Where, in first line, 2 means "2 segments" and 3 means "3 points". The 2 segments are "0 to 5" and "8 to 10", and the points to look for are 1, 6, 11. The output is

1 0 0

Where point 1 is in segment "0 to 5", and point 6 and 11 are not in any segment. If a point appears in more than one segment, like a 3, the output would be 2.

The original code, was just a double loop to search the points between segments. I used the Java Arrays quicksort (modified so when it sorts endpoints of segments, sorts also startpoints so start[i] and end[i] belong to the same segment i) to improve the speed of the double loop but it isnt enought.

The next code works fine but when there's too many segments it gets very slow:

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

I believe the problem is in the CountSegments() method but I'm not sure of another way to solve it. Supposedly, I should use a divide and conquer algorithm, but after 4 days, I'm up to any solution. I found a similar problem in CodeForces but the output is different and most solutions are in C++. Since I have just 3 months that I started to learn java, I think I have reached my knowledge limit.

Answer 1

Given the constrains by OP, let n be the # of segments, m be the number of points to be query, where n,m <= 5*10^4, I can come up with a O(nlg(n) + mlg(n)) solution (which should be enough to pass most online judge)

As each query is a verifying problem: Can the point be covered by some intervals, yes or no, we do not need to find which / how many intervals the point has been covered.

Outline of the algorithm:

1. Sort all intervals first by starting point, if tie then by length (rightmost ending point)
2. Try to merge the intervals to get some disjoint overlapping intervals. For e.g. (0,5), (2,9), (3,7), (3,5), (12,15) , you will get (0,9), (12,15). As the intervals are sorted, this can be done greedily in O(n)
3. Above are the precomputation, now for each point, we query using the disjoint intervals. Simply binary search if any interval contains such point, each query is O(lg(n)) and we got m points, so total O(m lg(n))

Combine whole algorithm, we will get an O(nlg(n) + mlg(n)) algorithm

Answer 2

This is an implementation similar to @Shole's idea:

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

It prints:

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