找出每个点包含多少个矩形

Question

我有

n

送货员详细信息。位于

(x,y)

点的送货员可以送货到具有

4

角

(0,0), (x,0), (y,0), (x,y)

的矩形中的所有点。 我们在同一地点没有多名送货员。

给定一个送货点坐标

(a,b)

，找出有多少送货员可以送货到该点。

示例：

Deliver person locations = [[1,2], [2,3], [1,5]]
Delivery points = [[1,1], [1,4]]

结果

[3,1]

说明：

Point [1,1] can be delivered by [1,2], [2,3], [1,5]
Point [1,4] can be delivered by [1,5]

限制：

number of locations and points range from 1 to 10^5
Delivery person location x and y range from 1 to 10^9
Deliver points location x is in range 1 to 10^9
Deliver points location y is in range 1 to 10^9

这是我的代码：

import java.util.*;

public class Main {
    public static List<Integer> solve(List<int[]> persons, List<int[]> locations) {
        List<Integer> ar = new ArrayList<>();
        persons.sort((p1, p2) -> Integer.compare(p2[1], p1[1]));
        for (int[] r : locations) {
            int x = r[0];
            int y = r[1];
            int total = 0;
            for (int[] p : persons) {
                int x1 = p[0];
                int y1 = p[1];
                if (y1 < y) {
                    break;
                }
                if (x1 >= x && y1 >= y) {
                    total++;
                }
            }
            ar.add(total);
        }
        return ar;
    }

    public static void main(String[] args) {
        // Example usage
        List<int[]> retailers = new ArrayList<>();
        retailers.add(new int[]{1, 2});
        retailers.add(new int[]{2, 3});
        retailers.add(new int[]{1, 5});

        List<int[]> requests = new ArrayList<>();
        requests.add(new int[]{1, 1});
        requests.add(new int[]{1, 4});

        List<Integer> result = solve(retailers, requests);
        System.out.println(result); // Output: [3, 1]
    }
}

如果

m

是位置大小，

n

是人员大小，那么我的代码复杂度是

n * log(n) + m*n

我想降低代码的时间复杂度，解决这个问题的正确方法是什么？

Answer 1

这可以通过线扫描来解决。首先，将所有 y 坐标压缩到范围

[0, 2 * 10^5 - 1]

。然后，可以使用二叉索引树来维护每个矩形未覆盖的范围。

时间复杂度：

O((M + N) * log(M + N))

public static int[] solve(List<int[]> persons, List<int[]> locations) {
    class BIT {
        int[] bit;
        BIT(int n) {
            bit = new int[n];
        }
        void update(int i, int v) {
            for (; i < bit.length; i |= i + 1) bit[i] += v;
        }
        int query(int i) {
            int ret = 0;
            for (; i >= 0; i = (i & (i + 1)) - 1) ret += bit[i];
            return ret;
        }
    }
    record Event(int[] point, int queryIdx) {}
    var ys = new ArrayList<Integer>();
    var evs = new ArrayList<Event>();
    for (var person : persons) {
        ys.add(person[1]);
        evs.add(new Event(person, -1));
    }
    for (int i = 0; i < locations.size(); i++) {
        var loc = locations.get(i);
        ys.add(loc[1]);
        evs.add(new Event(loc, i));
    }
    evs.sort(Comparator.comparingInt((Event ev) -> ev.point[0]).thenComparingInt(ev -> -ev.queryIdx));
    ys.sort(null);
    var bit = new BIT(ys.size());
    for (var person : persons) bit.update(Collections.binarySearch(ys, person[1]) + 1, 1);
    var ans = new int[locations.size()];
    for (var ev : evs)
        if (ev.queryIdx < 0) {
            bit.update(Collections.binarySearch(ys, ev.point[1]) + 1, -1);
            bit.update(0, 1);
        }
        else ans[ev.queryIdx] = persons.size() - bit.query(Collections.binarySearch(ys, ev.point[1]));
    return ans;
}