avatar

区间合并

区间合并

输入区间:按照左端点排序

模板

void merge(vector<PII> &segs)
{
vector<PII> res;

sort(segs.begin(), segs.end());

int st = -2e9, ed = -2e9;
for (auto seg : segs)
if (ed < seg.first)
{
if (st != -2e9) res.push_back({st, ed});
st = seg.first, ed = seg.second;
}
else ed = max(ed, seg.second);

if (st != -2e9) res.push_back({st, ed});

segs = res;
}

题目

AcWing

  • 805 区间合并

805

描述

给定 n 个区间 ,要求合并所有有交集的区间。

注意如果在端点处相交,也算有交集。

输出合并完成后的区间个数。

例如:[1,3]和[2,6]可以合并为一个区间[1,6]。

解答
import java.util.*;
import java.io.*;

public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());

// nums[0]左端点 nums[1]右端点
int[][] nums = new int[n][2];
for(int i=0;i<n;i++)
{
String[] strs = br.readLine().split(" ");
nums[i][0] = Integer.parseInt(strs[0]);
nums[i][1] = Integer.parseInt(strs[1]);

}

Arrays.sort(nums, new Comparator<int[]>(){
public int compare(int[] o1, int[] o2){
return o1[0]-o2[0];
}
});

int end = Integer.MIN_VALUE;
int sum = 0;


for(int st=0;st<n;st++){
if(nums[st][0]>end){
//无法合并
sum++;
}

//跟新end
end = Math.max(end, nums[st][1]);
}
System.out.println(sum);
}


}

Others

人无完人,何况是小白Chen我呢,文章难免会出现一些错误,若是读者们发现错误,可以评论或者联系我,Chen会尽力改正,给大家更优秀的博文。

文章作者: Chen
文章链接: https://vccyb.gitee.io/myblog/2020/03/22/Algorithm/articleM-10/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 东川
打赏
  • 微信
    微信
  • 支付寶
    支付寶

评论