题目描述
给定 n 个区间 [li,ri],要求合并所有有交集的区间。
注意如果在端点处相交,也算有交集。
输出合并完成后的区间个数。
例如:[1,3]和[2,6]可以合并为一个区间[1,6]。
输入格式
第一行包含整数n。
接下来n行,每行包含两个整数 l 和 r。
输出格式
共一行,包含一个整数,表示合并区间完成后的区间个数。
数据范围
1≤n≤100000,
−109≤li≤ri≤109
输入样例:
5
1 2
2 4
5 6
7 8
7 9
输出样例:
3
观众老爷们,如果本思路对您有帮助,求关注一波~~~
思路
本题思路很简单,采用的思想是贪心
多个区间[l1, r1] [12, r2] .... [ln, rn]
先对左端点l进行排序
初始化头start = -1e8 end = -1e8 记录开头结尾位置
如果两个区间之间有交集(第一个区间的尾部 >= 第二个区间的头部),则合并,更新尾部end = max(end, 第二个区间和第一个区间哪个尾部值最大)
否则重新标记新的区间头start和尾部end为第二个区间的头和尾
```
void merge(vector<PII> &segs){
vector<PII> res;
sort(segs.begin(), segs.end());
int start = -2e9, end = -2e9; //比较合并的空间大小
for(auto seg : segs){
if(end < seg.first){ //没有交集 (当前区间的左端点 > 维护的尾端点)
if(start != -2e9) res.push_back({start, end}); //将上一次存储的区间进行保存
start = seg.first, end = seg.second;
}else{
end = max(end, seg.second);
}
}
if(start != -2e9) res.push_back({start, end}); //将剩余的区间保存
segs = res;
}
```
java
//单纯的计算区间数
import java.util.Arrays;
import java.util.Scanner;
class Node {
int l;
int r;
public Node(int l, int r) {
this.l = l;
this.r = r;
}
}
public class Main {
static int n;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
Node[] nodes = new Node[n];
for (int i = 0; i < n; i++) {
int l = sc.nextInt();
int r = sc.nextInt();
nodes[i] = new Node(l, r);
}
int res = merge(nodes);
System.out.println(res);
}
private static int merge(Node[] nodes) {
Arrays.sort(nodes, (o1, o2) -> {return o1.l - o2.l;});
int cnt = 0;
int max = Integer.MIN_VALUE;
for (int i = 0; i < n; i ++) {
if (max < nodes[i].l) cnt ++;
max = Math.max(max, nodes[i].r);
}
return cnt;
}
}
// 合并区间
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
class Node{
int l;
int r;
public Node(int l, int r) {
this.l = l;
this.r = r;
}
}
public class Main {
static int n;
static int N = 200010;
static Node[] segs;
static List<Node> res = new ArrayList<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
segs = new Node[n];
for (int i = 0; i < n; i++) {
int l = sc.nextInt();
int r = sc.nextInt();
segs[i] = new Node(l, r);
}
int res = merge(segs);
System.out.println(res);
}
private static int merge(Node[] segs) {
Arrays.sort(segs, (o1, o2) -> {return o1.l - o2.l;});
int start = Integer.MAX_VALUE, end = Integer.MIN_VALUE;
for (int i = 0; i < segs.length; i++) {
int l = segs[i].l;
int r = segs[i].r;
if (end < l) {
if (start != Integer.MAX_VALUE) {
res.add(new Node(start, end));
}
start = l;
end = r;
} else {
end = Math.max(end, r);
}
}
if (start != Integer.MAX_VALUE) {
res.add(new Node(start, end));
}
return res.size();
}
}
// 数组的方式处理
import java.util.Scanner;
import java.util.Arrays;
public class Main{
static int n;
static int N = 200010; //2n
static int[][] segs, res;
static int segSize = 0; //统计segs区间的个数
static int resSize = 0; //统计合并后区间的个数
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
segs = new int[n][2];
res = new int[n][2];
for(int i = 0; i < n; i ++){
segs[i][0] = sc.nextInt();
segs[i][1] = sc.nextInt();
segSize ++;
}
merge(segs);
System.out.println(resSize);
}
public static void merge(int[][] segs){
Arrays.sort(segs, (o1, o2) -> o1[0] - o2[0]);
int start = Integer.MAX_VALUE, end = Integer.MIN_VALUE; // 保证第一次记录值
int j = 0;
for(int i = 0; i < segSize; i ++){
int l = segs[i][0], r = segs[i][1];
if(end < l){
if(start != Integer.MAX_VALUE){
res[j][0] = l;
res[j][1] = r;
j ++;
resSize ++;
}
start = l;
end = r;
}else{
end = Math.max(end, r);
}
}
if(start != Integer.MAX_VALUE){
res[j][0] = start;
res[j][1] = end;
resSize ++;
}
}
}
python
segs = list()
res = list()
def merge(segs):
global res
start, end = -1e9 + 10, -1e9 + 10
for i in range(len(segs)):
l, r = segs[i][0], segs[i][1]
if(end < l):
if(start != -1e9 + 10):
res.append([start, end])
start, end =l, r
else:
end = max(end, r)
if(start != -1e9 + 10):
res.append([start, end])
def main():
global segs, res
n = int(input());
for i in range(n):
segs.append(list(map(int, input().split(" "))))
segs.sort(key = lambda x : x[0])
merge(segs)
print(len(res))
main()
c++
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 100010;
int n;
vector<PII> segs;
void merge(vector<PII> &segs){
vector<PII> res;
sort(segs.begin(), segs.end());
int start = -2e9, end = -2e9;
for(auto seg : segs){
if(end < seg.first){ //没有交集 (当前区间的左端点 > 维护的尾端点)
if(start != -2e9) res.push_back({start, end}); //将上一次存储的区间进行保存
start = seg.first, end = seg.second; //记录当前的区间
}else{
end = max(end, seg.second);
}
}
if(start != -2e9) res.push_back({start, end}); //将剩余的区间保存
segs = res;
}
int main(){
cin >> n;
for(int i = 0; i < n; i ++){
int l, r;
cin >> l >> r;
segs.push_back({l, r});
}
merge(segs);
cout << segs.size() << endl;
return 0;
}
您的java数组模板很有用,我当初用的
List<int[]> L = new ArrayList<>((int)1e5 + 5);
模板,去做管道时卡壳了,还是得数组模板才行