Q12 PepCoding | Maximum Non-overlapping Bridges

PHOTO EMBED

Thu Mar 02 2023 12:55:37 GMT+0000 (Coordinated Universal Time)

Saved by @Ayush_dabas07 

import java.io.*;
import java.util.*;

public class Main {
    public static class bridge implements Comparable<bridge>{
        int north , south ;
        
        bridge(){
            
        }
        bridge(int north ,int south){
            this.north = north;
            this.south = south;
        }
        
        //this - other = ascending order , other - this = descending
        public int compareTo(bridge o){
            
       //if north coordinates are equal sort in ascending order of south
            if(this.north == o.north)
            return this.south - o.north;
            
            //else sort in ascending order of north only
            else
            return this.north - o.north;
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int n = Integer.parseInt(br.readLine());
      bridge[] brdgs = new bridge[n];
      for (int i = 0; i < brdgs.length; i++) {
         String str = br.readLine();
         brdgs[i] = new bridge();
         brdgs[i].north = Integer.parseInt(str.split(" ")[0]);
         brdgs[i].south = Integer.parseInt(str.split(" ")[1]);
      }
      
      Arrays.sort(brdgs);   //sort in ascending order of north
      
      //now LIS based on south coordinate
      
      System.out.println(LIS(brdgs));
    }
    
    public static int LIS(bridge[] brdgs){
        int n= brdgs.length;
        int[] LIS = new int[n];
        
      //for first bridge it can only make 1 maximum non overlapping bridge
        LIS[0] = 1; 
        
        int ans = 1;
        for(int i = 1 ; i < n ; i++){
            
        //checking all bridges before current which have south coordinate         // smaller than current 
            for(int j = i-1 ; j >= 0 ; j--){
                if(brdgs[j].south < brdgs[i].south){
                    LIS[i] = Math.max(LIS[i],LIS[j]);
                }
            }
            LIS[i] += 1;    //adding length 1 for current bridge
            
            ans = Math.max(ans , LIS[i]);
        }
        
        return ans;
    }
    

}
content_copyCOPY

https://www.pepcoding.com/resources/data-structures-and-algorithms-in-java-levelup/dynamic-programming/max-non-overlapping-bridges-official/ojquestion