城市间最大不重叠桥梁的算法

Question

河的两边有相等数量的城市。从一侧的城市到另一侧的城市的桥由1#Y3表示，其中城市1在下侧，桥到城市3在上侧。我们必须找到最大数量的非重叠桥。因此对于输入的1#Y2、2#Y4、3#Y1、4#Y5、5#Y3、6#Y6输出将是4,因为1#Y2、2#Y4、4#Y5、6#Y6是不重叠的。

这是我的密码-

public static int maxNonOverlappingBridges(String input1[]) {
    int result = 0;
    for (int i = 0; i < input1.length; i++) {
        int total = 1;
        int notCrossing = Integer.parseInt(input1[i].substring(input1[i].length() - 1));
        for (int j = 0; j < input1.length; j++) {
            if (j < i) {
                if (Integer.parseInt(input1[j].substring(input1[j].length() - 1)) < notCrossing) {
                    total += 1;
                    notCrossing = Integer.parseInt(input1[j].substring(input1[j].length() - 1));
                }
            } else if (j > i) {
                if (Integer.parseInt(input1[j].substring(input1[j].length() - 1)) > notCrossing) {
                    total += 1;
                    notCrossing = Integer.parseInt(input1[j].substring(input1[j].length() - 1));
                }
            } else {
                notCrossing = Integer.parseInt(input1[j].substring(input1[j].length() - 1));
            }

        }
        if (total > result) result = total;
    }
    return result;
}

对此有没有更优化的算法？

Answer 1

这在O（nLog(n)）中运行。

public static int maxNonOverlappingBridges(String[] bridges) {
    int overlappings1 = 0;
    int overlappings2 = 0;
    int maxIndexOfCityOnOtherSide = 0;

    /*
     * Sorting bridge connections with respect to the left index. (i.e : 2 in 2#y4)
     * O(n*log(n)) time
     */      
    Arrays.sort(bridges);

    List<Integer[]> brigesAsArray = new ArrayList<>();

    Integer[] previousBridge = null; 

    for(String b: bridges){

        if(previousBridge == null){
            String[] bridgeIndexes = b.split("#y");
            previousBridge = new Integer[]{Integer.parseInt(bridgeIndexes[0]),Integer.parseInt(bridgeIndexes[1])};
            maxIndexOfCityOnOtherSide = previousBridge[1];              
            brigesAsArray.add(previousBridge);
            continue;
        }

        String[] bridgeIndexes = b.split("#y");
        Integer[] currentBridge = new Integer[]{Integer.parseInt(bridgeIndexes[0]),Integer.parseInt(bridgeIndexes[1])};

        if(currentBridge[1] < maxIndexOfCityOnOtherSide){
            //overlapping found;
            overlappings1++;
        }else{
            maxIndexOfCityOnOtherSide = currentBridge[1];
        }

        previousBridge = currentBridge;
        brigesAsArray.add(previousBridge);
    }       

    Integer[][] bridgeIndexes = brigesAsArray.toArray(new Integer[0][0]);
    brigesAsArray.toArray(bridgeIndexes);       

    /*
     * Sorting bridge connections with respect to the right index. (i.e : 4 in 2#y4)
     * O(n*log(n)) time
     */ 

    Arrays.sort(bridgeIndexes, new Comparator<Integer[]>() {
        @Override
        public int compare(Integer[] o1, Integer[] o2) {
            return Integer.compare(o1[1], o2[1]);
        }           
    });

    previousBridge = null;

    for(Integer[] b: bridgeIndexes){

        if(previousBridge == null){
            maxIndexOfCityOnOtherSide = b[0];   
            previousBridge = b;
            continue;
        }

        if(b[0] < maxIndexOfCityOnOtherSide){
            //overlapping found;
            overlappings2++;
        }else{
            maxIndexOfCityOnOtherSide = b[0];
        }

        previousBridge = b;
        brigesAsArray.add(previousBridge);
    }   
    return (bridges.length - Math.min(overlappings1, overlappings2));
}

希望这有帮助。