Dynamic Programming | Building Bridges

// Java Program for maximizing the no. of bridges
// such that none of them cross each other

import java.util.*;

class CityPairs // Create user-defined class
{
    int north, south;
    CityPairs(int north, int south) // Constructor
    {
        this.north = north;
        this.south = south;
    }
}
// Use Comparator for manual sorting
class MyCmp implements Comparator<CityPairs> 
{
    public int compare(CityPairs cp1, CityPairs cp2)
    {
        // If 2 cities have same north coordinates
        // then sort them in increasing order
        // according to south coordinates.
        if (cp1.north == cp2.north)
            return cp1.south - cp2.south;

        // Sort in increasing order of
        // north coordinates.
        return cp1.north - cp2.north;
    }
}
public class BuildingBridges {
    // function to find the max. number of bridges
    // that can be built
    public static int maxBridges(CityPairs[] pairs, int n)
    {
        int[] LIS = new int[n];
        // By default single city has LIS = 1.
        Arrays.fill(LIS, 1);

        Arrays.sort(pairs, new MyCmp()); // Sorting->
                                         // calling
        // our self made comparator

        // Logic for Longest increasing subsequence
        // applied on south coordinates.
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (pairs[i].south >= pairs[j].south)
                    LIS[i] = Math.max(LIS[i], LIS[j] + 1);
            }
        }
        int max = LIS[0];
        for (int i = 1; i < n; i++) {
            max = Math.max(max, LIS[i]);
        }

        // Return the max number of bridges that can be
        // built.
        return max;
    }

    // Driver Program to test above
    public static void main(String[] args)
    {
        int n = 4;
        CityPairs[] pairs = new CityPairs[n];
        pairs[0] = new CityPairs(6, 2);
        pairs[1] = new CityPairs(4, 3);
        pairs[2] = new CityPairs(2, 6);
        pairs[3] = new CityPairs(1, 5);
        System.out.println("Maximum number of bridges = "
                           + maxBridges(pairs, n));
    }
}

import java.util.*;

public class Main {

    public static int non_overlapping_bridges(ArrayList<Pair<Integer, Integer>> temp, int n) {
        // Step - 1 Sort the north side.
        Collections.sort(temp);
        // Create the Dp array to store the flow of non overlapping bridges.
        // ans-->Store the final max number of non-overlapping bridges.
        ArrayList<Integer> dp = new ArrayList<>(Collections.nCopies(n + 1, Integer.MAX_VALUE));
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int idx = Collections.binarySearch(dp, temp.get(i).second);
            if (idx < 0) {
                idx = -idx - 1;
            }
            dp.set(idx, temp.get(i).second);
            ans = Math.max(ans, idx + 1);
        }
        return ans;
    }

    public static void main(String[] args) {
        int n = 4;
        ArrayList<Pair<Integer, Integer>> temp = new ArrayList<>();
        temp.add(new Pair<Integer, Integer>(6, 2));
        temp.add(new Pair<Integer, Integer>(4, 3));
        temp.add(new Pair<Integer, Integer>(2, 6));
        temp.add(new Pair<Integer, Integer>(1, 5));

        System.out.println(non_overlapping_bridges(temp, n));
    }

    static class Pair<A extends Comparable<A>, B extends Comparable<B>> implements Comparable<Pair<A, B>> {
        A first;
        B second;

        public Pair(A first, B second) {
            this.first = first;
            this.second = second;
        }

        @Override
        public int compareTo(Pair<A, B> o) {
            int cmp = first.compareTo(o.first);
            if (cmp != 0) return cmp;
            return second.compareTo(o.second);
        }
    }
}