题目描述
偷懒没有用小根堆来做 刚开始正序遍历超时了, 然后想想可能应该是正序遍历的次数太多了 就试了一下倒叙然后过了(偷懒不可取)
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter outer = new BufferedWriter(new OutputStreamWriter(System.out));
static int N = 100010;
static int[] p = new int[N]; // 分别存左右端点
static List<Node> lists = new ArrayList<>();
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(reader.readLine().trim());
for(int i = 1; i <= n; i++){
String[] s = reader.readLine().split(" ");
int l = Integer.parseInt(s[0]), r = Integer.parseInt(s[1]);
lists.add(new Node(l,r));
}
lists.sort(new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
return o1.l-o2.l;
}
});
int idx = 0;
for (Node list : lists) {
//System.out.println(list.l+" "+list.r);
boolean flag = false;
for(int i = idx; i >=1; i--){
if(p[i] < list.l){
p[i] = list.r;
flag = true;
break;
}
}
if(!flag){
p[++idx] = list.r;
}
//System.out.println("idx: "+idx+" "+p[idx]);
}
outer.write(idx+"\n");
outer.flush();
outer.close();
reader.close();
}
}
class Node{
public int l;
public int r;
public Node(int l, int r){
this.l = l;
this.r = r;
}
public int getL() {
return l;
}
public void setL(int l) {
this.l = l;
}
public int getR() {
return r;
}
public void setR(int r) {
this.r = r;
}
}
求关注