Java 同学需要注意,这题是日常使用 sout 过不了系列
import java.util.*;
import java.io.*;
class Range {
int l, r;
int idx;
public Range(int _l, int _r, int _idx) {
l = _l;
r = _r;
idx = _idx;
}
}
class Main {
public static void main(String[] args) throws IOException {
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter w = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(read.readLine());
Range[] rs = new Range[n];
for (int i = 0; i < n; i++) {
String[] s = read.readLine().split(" ");
int l = Integer.parseInt(s[0]);
int r = Integer.parseInt(s[1]);
rs[i] = new Range(l, r, i);
}
Arrays.sort(rs, (a, b) -> {
return a.l - b.l;
});
int[] nums = new int[n];
List<Integer> list = new ArrayList<>(); // 存放该分组的右端点最大值
for (int i = 0; i < n; i++) {
Range range = rs[i];
boolean isJoin = false;
for (int j = 0; j < list.size(); j++) {
int maxR = list.get(j);
if (range.l > maxR) {
list.set(j, range.r);
nums[range.idx] = j + 1;
isJoin = true;
break;
}
}
if (!isJoin) {
list.add(range.r);
nums[range.idx] = list.size();
}
}
w.write(list.size() + "\n");
for (int i = 0; i < n; i++) w.write(nums[i] + "\n");
w.flush();
w.close();
read.close();
}
}
由于每次都是寻找可以加入的组(从已有组中的最小右端点开始找),可以使用小根堆优化
import java.util.*;
import java.io.*;
class Range {
int l, r;
int idx;
public Range(int _l, int _r, int _idx) {
l = _l;
r = _r;
idx = _idx;
}
}
class Main {
public static void main(String[] args) throws IOException {
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter w = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(read.readLine());
Range[] rs = new Range[n];
for (int i = 0; i < n; i++) {
String[] s = read.readLine().split(" ");
int l = Integer.parseInt(s[0]);
int r = Integer.parseInt(s[1]);
rs[i] = new Range(l, r, i);
}
Arrays.sort(rs, (a, b) -> {
return a.l - b.l;
});
int[] nums = new int[n];
PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> { // 小根堆,存放的是该组的最大值和组编号
return a[0] - b[0];
});
for (int i = 0; i < n; i++) {
Range range = rs[i];
if (!q.isEmpty() && range.l > q.peek()[0]) {
int[] num = q.poll();
num[0] = range.r;
q.add(num);
nums[range.idx] = num[1];
} else {
q.add(new int[]{range.r, q.size() + 1});
nums[range.idx] = q.size();
}
}
w.write(q.size() + "\n");
for (int i = 0; i < n; i++) w.write(nums[i] + "\n");
w.flush();
w.close();
read.close();
}
}