链接
来源:牛客网
每一个线段都有start和end两个数据项,表示这条线段在X轴上从start位置开始到end位置结束。
给定一批线段,求所有重合区域中最多重合了几个线段,首尾相接的线段不算重合。
例如:线段[1,2]和线段[2.3]不重合。
线段[1,3]和线段[2,3]重合
串气球
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int n = in.nextInt();
int[] count = new int[100001];
while (n -- > 0) {
int a = in.nextInt();
int b = in.nextInt();
count[a] ++;
count[b] --;
}
int res = 0, sum = 0;
for (int i = 1; i <= 100000; ++i) {
sum += count[i];
res = Math.max(res, sum);
}
System.out.println(res);
}
}
}
串气球(离散化)
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.TreeSet;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int n = in.nextInt();
Map<Integer, Integer> countMap = new TreeMap<>();
while (n -- > 0) {
int a = in.nextInt();
int b = in.nextInt();
Integer exist = countMap.getOrDefault(a, 0);
countMap.put(a, exist + 1);
exist = countMap.getOrDefault(b, 0);
countMap.put(b, exist - 1);
}
int res = 0, sum = 0;
for (Map.Entry<Integer, Integer> entry: countMap.entrySet()) {
sum += entry.getValue();
res = Math.max(sum, res);
}
System.out.println(res);
}
}
}
线段树
import java.util.*;
public class Main {
static class SegmentTree {
private int[] max;
private int[] lazy;
public SegmentTree(int n) {
this.max = new int[n << 2 ^ 1];
this.lazy = new int[n << 2 ^ 1];
}
private void pushUp(int rt) {
max[rt] = Math.max(max[rt << 1], max[rt << 1 ^ 1]);
}
private void pushDown(int rt) {
if (lazy[rt] != 0) {
max[rt << 1] += lazy[rt];
lazy[rt << 1] += lazy[rt];
max[rt << 1 ^ 1] += lazy[rt];
lazy[rt << 1 ^ 1] += lazy[rt];
lazy[rt] = 0;
}
}
public void add(int L, int R, int C, int l, int r, int rt) {
if (L <= l && r <= R) {
max[rt] += C;
lazy[rt] += C;
return;
}
int mid = (l + r) >> 1;
pushDown(rt);
if (L <= mid) {
add(L, R, C, l, mid, rt << 1);
}
if (mid < R) {
add(L, R, C, mid + 1, r, rt << 1 ^ 1);
}
pushUp(rt);
}
public int query(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R) {
return max[rt];
}
int mid = (l + r) >> 1;
pushDown(rt);
int res = 0;
if (L <= mid) {
res = Math.max(res, query(L, R, l, mid, rt << 1));
}
if (mid < R) {
res = Math.max(res, query(L, R, mid + 1, r, rt << 1 ^ 1));
}
return res;
}
}
private static Map<Integer, Integer> discrete(int[][] data) {
if (data == null || data.length == 0) {
return new HashMap<>(0);
}
TreeSet<Integer> treeSet = new TreeSet<>();
for (int[] item : data) {
treeSet.add(item[0]);
treeSet.add(item[1] - 1);
}
Map<Integer, Integer> res = new HashMap<>();
int count = 0;
for (int item : treeSet) {
res.put(item, ++count);
}
return res;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int n = in.nextInt();
int[][] arr = new int[n][2];
for (int i = 0; i < n; ++i) {
arr[i][0] = in.nextInt();
arr[i][1] = in.nextInt();
}
Map<Integer, Integer> discrete = discrete(arr);
int m = discrete.size();
SegmentTree segmentTree = new SegmentTree(m);
int res = 0;
for (int[] item : arr) {
int L = discrete.get(item[0]);
int R = discrete.get(item[1] - 1);
segmentTree.add(L, R, 1, 1, m, 1);
int max = segmentTree.query(L, R, 1, m, 1);
res = Math.max(res, max);
}
System.out.println(res);
}
}
}
堆
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int n = in.nextInt();
int[][] data = new int[n][2];
for (int i = 0; i < n; ++i) {
data[i][0] = in.nextInt();
data[i][1] = in.nextInt();
}
Arrays.sort(data, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
int res = 0;
for (int i = 0; i < n; ++i) {
while (! priorityQueue.isEmpty() && priorityQueue.peek() <= data[i][0]) {
priorityQueue.poll();
}
priorityQueue.offer(data[i][1]);
res = Math.max(res, priorityQueue.size());
}
System.out.println(res);
}
}
}