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;
}
}
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter