Today, I. have solved Problem D of AtCoder Beginner Contest 230. I have solved it by sorting by right coordinates and increasing the answer by 1 if the left coordinate is greater than the slide.
After the contest ends, I was wondering why sorting by left coordinate does not work and gave WA. Please provide a test case where this fails. Thank You!
Problem: D - Destroyer Takahashi
AC Solution:
import java.util.*;
import java.io.*;
import java.math.*;
public class Main {
static StringBuffer str=new StringBuffer();
static long n,d;
static List<long []> l;
static void solve(){
Collections.sort(l, (a, b) -> {
return (int)(a[1]-b[1]);
});
long ans=0;
long x=-(1l<<40);
for(long []li:l){
if(x+d-1 < li[0]){
x=li[1];
ans++;
}
}
str.append(ans).append("\n");
}
public static void main(String[] args) throws java.lang.Exception {
BufferedReader bf;
PrintWriter pw;
boolean lenv=false;
if(lenv){
bf = new BufferedReader(
new FileReader("input.txt"));
pw=new PrintWriter(new
BufferedWriter(new FileWriter("output.txt")));
}else{
bf = new BufferedReader(new InputStreamReader(System.in));
pw = new PrintWriter(new OutputStreamWriter(System.out));
}
// int t = Integer.parseInt(bf.readLine().trim());
// while (t-- > 0) {
l=new ArrayList<>();
String []s=bf.readLine().trim().split("\\s+");
n=Long.parseLong(s[0]);
d=Long.parseLong(s[1]);
for(int i=0;i<n;i++){
s=bf.readLine().trim().split("\\s+");
l.add(new long[]{Long.parseLong(s[0]), Long.parseLong(s[1])});
}
solve();
// }
pw.print(str);
pw.flush();
// System.outin.print(str);
}
}
WA solution
import java.util.*;
import java.io.*;
import java.math.*;
public class Main {
static StringBuffer str=new StringBuffer();
static long n,d;
static List<long []> l;
static void solve(){
Collections.sort(l, (a, b) -> {
return (int)(a[0]-b[0]);
});
long ans=0;
long x=-(1l<<40);
for(long []li:l){
if(x+d-1 < li[0]){
x=li[1];
ans++;
}
}
str.append(ans).append("\n");
}
public static void main(String[] args) throws java.lang.Exception {
BufferedReader bf;
PrintWriter pw;
boolean lenv=false;
if(lenv){
bf = new BufferedReader(
new FileReader("input.txt"));
pw=new PrintWriter(new
BufferedWriter(new FileWriter("output.txt")));
}else{
bf = new BufferedReader(new InputStreamReader(System.in));
pw = new PrintWriter(new OutputStreamWriter(System.out));
}
// int t = Integer.parseInt(bf.readLine().trim());
// while (t-- > 0) {
l=new ArrayList<>();
String []s=bf.readLine().trim().split("\\s+");
n=Long.parseLong(s[0]);
d=Long.parseLong(s[1]);
for(int i=0;i<n;i++){
s=bf.readLine().trim().split("\\s+");
l.add(new long[]{Long.parseLong(s[0]), Long.parseLong(s[1])});
}
solve();
// }
pw.print(str);
pw.flush();
// System.outin.print(str);
}
}