Untitled

import java.util.Arrays;

public class BuildingBridgesDP {
    public int maxBridges(int[] north, int[] south) {
        int n = north.length;

        // Step 1: Create pairs and sort them
        int[][] bridges = new int[n][2];
        for (int i = 0; i < n; i++) {
            bridges[i][0] = north[i];
            bridges[i][1] = south[i];
        }

        // Sort by north, and by south descending if north values are equal
        Arrays.sort(bridges, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);

        // Step 2: Extract south values
        int[] southCoords = new int[n];
        for (int i = 0; i < n; i++) {
            southCoords[i] = bridges[i][1];
        }

        // Step 3: DP to find LIS ending at each index
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int maxLIS = 1;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (southCoords[i] > southCoords[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLIS = Math.max(maxLIS, dp[i]);
        }

        return maxLIS;
    }

    public static void main(String[] args) {
        BuildingBridgesDP bb = new BuildingBridgesDP();

        int[] north = {1, 3, 2, 4};
        int[] south = {2, 3, 1, 4};
        System.out.println(bb.maxBridges(north, south)); // Output: 3
    }
}