如何找到所有不重叠的组合

Question

给定一条长度为 N 的直线，索引位置从 1 开始，而不是 0。

使用 startIndex 和 endIndex 对在此线上标记点。

计算不相交对的总数

示例：

开始 = [1, 4, 6, 7] 结束 = [3, 5, 8, 10]

1 2 3 4 5 6 7 8 9 10
|----|              1 to 3
      |-|           4 to 5
         |----|         6 to 8
        |------|        7 to 10

We can select a pair if they are not overlapping.

Available pairs are:

1 -> (1,3)
2 -> (4,5)
3 -> (6, 8)
4 -> (7, 10)
The following combinations can be chosen:
• 1 and 2
• 1 and 3
• 1 and 4
• 2 and 3
• 2 and 4


So we have 5 possible nonoverlapping pairs

Result = 5

限制：

array values in range 1 to 10^9
length of starting and ending arrays is 1 to 10^5

现在，当输入有重复的开始或结束时间条目时，我陷入困境。

这是我的代码，仅当输入没有重复项时才有效，但坚持逻辑来查找重复条目的总和。

public static long solve(int N, List<Integer> starting, List<Integer> ending) {
    int n = starting.size();
    List<int[]> list = new ArrayList<>();
    for(int i=0; i<n; i++) {
        list.add(new int[]{starting.get(i), ending.get(i), i});
    }

    list.sort((e1, e2) -> {
        int e = e1[0] - e2[0];
        if(e ==0) e = e1[1] - e2[1];
        return e;
    });
    for(int[] e : list) {
        System.out.print(Arrays.toString(e) + " : ");
    }
    System.out.println();
    TreeMap<Integer, List<int[]>> tree = new TreeMap<>();

    for(int i=0; i<n; i++) {
        int[] ar = list.get(i);
        int start = ar[0];
        int end = ar[1];
        int pos = ar[2];
        List<int[]> value = tree.getOrDefault(start, new ArrayList<>());
        tree.put(start, value);
        value.add(new int[]{end , pos});
    }
    int index = 0;
    
    for(int k : tree.keySet()) {
        List<int[]> e = tree.get(k);
        for(int[] ar : e) {
            ar[1] = index;
        }
        index++;
    }
    int size = index;

    long result = 0;

    for(int key : tree.keySet()) {
        List<int[]> ar = tree.get(key);
        // stuck here, fix logic to handle duplicates
        int[] next = ar.get(0);
        Integer nextKey = tree.higherKey(next[0]);
        if(nextKey != null) {
            List<int[]> value = tree.get(nextKey);
            int[] nextArr = value.get(0);
            int position = nextArr[1];
            int diff =  (size - position);
            result += diff;
        }
    }
    return result;
}

我可以使用蛮力方法，但时间效率不高，那么如何解决这个问题？

具有重复项的示例测试用例：

案例1：

starting = 1, 1, 6, 7
ending = 5, 3, 8, 10

Expected result: 4

案例2：

Starting = 26, 49, 28, 10, 41, 83, 84, 1, 32, 20, 13, 74, 1, 3, 11, 5, 4, 74, 36, 14

Ending = 96, 78, 99, 59, 75, 99, 91, 73, 39, 96, 35, 81, 92, 39, 36, 33, 97, 95, 76, 73

Expected result : 52

Answer 1

分别对开始和结束进行排序。
遍历结局数组。
对于每个结尾，找到其后第一个开头的索引

i

并将

(n-i)

添加到结果（当前结尾之后的间隔数）

Python 代码作为概念证明（给出 52）

starting = [26, 49, 28, 10, 41, 83, 84, 1, 32, 20, 13, 74, 1, 3, 11, 5, 4, 74, 36, 14]
ending = [96, 78, 99, 59, 75, 99, 91, 73, 39, 96, 35, 81, 92, 39, 36, 33, 97, 95, 76, 73]
starting.sort()
ending.sort()
i = 0
n = len(starting)
res = 0
for x in ending:
    while (i < n) and (starting[i] <= x):
        i += 1
    res += (n-i)
print(res)