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