合并区间

'''
1.首先按照x元素排序，把第一个区间存入res
2.从第二个开始遍历：
如果当前区间与res[-1]无重叠，直接将当前区间append到res
如果有重叠，将res[-1]的end值更新为max(res[-1]的end值,当前区间end值)
'''
s = input()
s = s.split()
s = [i.split(',') for i in s]
s = [[int(j) for j in i] for i in s]
s.sort(key=lambda x:x[0])
##print(s)
res = [s[0]]
for i in range(1,len(s[1:])+1):
    if s[i][0]<=res[-1][1]:
        res[-1][1] = max(s[i][1],res[-1][1])
    else:
        res.append(s[i])
res = [','.join([str(j) for j in i]) for i in res]
res = ' '.join(res)
print(res)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

class Interval{
    int lower;
    int upper;
    Interval(int lower, int upper) {
        this.lower = lower;
        this.upper = upper;
    }
}

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().split(" ");
        Interval[] ins = new Interval[strs.length];
        for (int i = 0; i < strs.length; i++) {
            String[] arr = strs[i].split(",");
            ins[i] = new Interval(Integer.parseInt(arr[0]), Integer.parseInt(arr[1]));
        }

        Arrays.sort(ins, Comparator.comparingInt(o -> o.lower));

        int cur = 0;
        for (int i = 1; i < ins.length; i++) {
            if (ins[i].lower <= ins[cur].upper) {
                ins[cur].upper = Math.max(ins[cur].upper, ins[i].upper);
            } else {
                System.out.print(ins[cur].lower + "," + ins[cur].upper + " ");
                cur = i;
            }
        }

        System.out.println(ins[cur].lower + "," + ins[cur].upper);
    }
}

arr = [n for n in input().split()]
a = []
for i in range(len(arr)):
    a.append([int(n) for n in arr[i].split(',')])
a.sort()
i = 0
while i < len(a)-1:
    if a[i][1] < a[i+1][0]:
        i += 1
    elif a[i][1] >= a[i+1][0]:
        a[i] = [a[i][0], max(a[i][1], a[i+1][1])]
        a.remove(a[i+1])
for i in a:
    print(str(i[0])+","+str(i[1]), end=" ")

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        String s;
        Scanner cin = new Scanner(System.in);
        s = cin.nextLine();
        String[] str = s.split(" ");//以空格将字符串拆分成区间 a,b

        ArrayList<String> list = new ArrayList();//用来存放最终的输出结果
        String[][] temp = new String[str.length][];
        int[][] t = new int[str.length][2];

        for (int i = 0; i < str.length; i++){
            temp[i] = str[i].split(",");//以","将区间拆分成 a和b
            for (int j = 0; j < 2; j++)//t[i][0]表示左边界，t[i][1]表示右边界
                t[i][j] = Integer.parseInt(temp[i][j]);
        }
        //用冒泡排序将每个区间按左边界从小到大进行排序
        for (int i = 1; i < str.length-1; i++)
            for (int j = 0; j < str.length - i; j++)
                if (t[j + 1][0] < t[j][0]) {
                    t[j+1][0] = t[j][0] + t[j + 1][0];
                    t[j ][0] = t[j + 1][0] - t[j][0];
                    t[j+1][0] = t[j + 1][0] - t[j][0];
                    t[j+1][1] = t[j + 1][1] + t[j][1];
                    t[j ][1] = t[j + 1][1] - t[j][1];
                    t[j+ 1][1] = t[j + 1][1] - t[j][1];
                }
        //将排序后的第一个区间作为初始结果
        list.add(t[0][0] + "");
        list.add(",");
        list.add(t[0][1] + "");
        list.add(" ");
        
        for (int i = 1; i < str.length; i++) {
            //如果i区间的左边界大于合并区间的右边界，无交集，结果直接插入此区间
            if (t[i][0] > Integer.parseInt(list.get(list.size() - 2))) {
                list.add(t[i][0] + "");
                list.add(",");
                list.add(t[i][1] + "");
                list.add(" ");
            }
            //如果i区间的左边界小于合并区间的右边界且右边界大于合并区间的右边界，
            //则将合并区间右边界改为i区间右边界
            else if (t[i][1] > Integer.parseInt(list.get(list.size() - 2))) {
                list.set(list.size() - 2, t[i][1] + "");
            } else ;//其他情况说明合并区间包含i区间
        }
        
        for (String a : list)
            System.out.print(a);
    }
} 

	//借助数组



	#include<iostream>
using namespace std;
int main()
{
    int a[100]={0};
    int tmp1,tmp2;
    char ch;
    bool flag=false;
    while(cin>>tmp1>>ch>>tmp2)
    {
        for(int i=tmp1;i<tmp2;i++)
            a[i]=1;
        if(a[tmp2]!=1)
        a[tmp2]=2;
    }
    for(int i=0;i<100;i++)
    {
        if(a[i]==1)
        {
            if(flag==true)
            {
                flag=false;
                cout<<' ';
            }
            cout<<i<<',';
            while(a[++i]==1);
            cout<<i;
            flag=true;
        }
    }
    return 0;   
}



	//什么叫暴力Code...



	#include<iostream>



	#include<vector>



	#include<algorithm>



	using namespace std;



	int main()



	{



	vector<pair<int, int>> vec;



	int a, b;



	char ch;



	while(cin>>a>>ch>>b)



	{



	vec.push_back({ a,b });



	}



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



	vector<pair<int, int>>::iterator it;



	int max=0;



	for(it = vec.begin(); it < vec.end(); it++)



	{



	if(max<it->first)



	{  cout << it->first << ',';



	int tmp = it->second;



	if((it + 1) == vec.end())



	{



	cout << tmp;



	break;



	}



	while((it+=1) < vec.end())



	{



	if(tmp < it->first)



	{



	cout << tmp << ' ';



	it--;



	break;



	}



	else if(tmp < it->second)



	{



	if((it + 1) == vec.end())



	{



	cout << it->second; break;



	}



	else if((it + 1)->first == it->second)



	{



	tmp = it->second;



	}



	else if((it+1)->second<it->second&&it->second>(it+1)->first)



	{



	tmp=it->second;



	it++;



	}



	else//



	{



	cout << it->second << ' ';   break;



	}



	}



	else if(tmp > it->second && (it + 1) == vec.end())



	{



	cout << tmp;



	break;



	}



	}



	max=it->second;



	}



	}



	return 0;



	}

#include <iostream>
using namespace std;

int main(){
    static int arr[1000];
    char ch;
    int a,b;
    while(cin>>a>>ch>>b){
        // 将输入的区间映射到数组上，右端作为开区间（关键）
        for(int i=a;i<b;i++){
             arr[i]=1;
         }
     }
    int flag=0;
    for(int i=0;i<sizeof(arr)/sizeof(int);i++){
        if(flag==0&&arr[i]==1){
            cout<<i<<",";
            flag=1;
        }
        else if(flag==1&&arr[i]==0){
            cout<<i<<" ";
            flag=0;
        }
    }
     return 0;
 }

python3解法

leetcode上一道原题的变形, 解法如下：

def merge(intervals):
    """
    合并区间算法。
    :param intervals: 传入的区间数组。例如[[1, 3], [2, 5]]
    :return: 合并后的区间。例如[[1, 5]]
    """
    out = []
    for i in sorted(intervals, key=lambda i: i[0]):  # 对区间进行排序
        if out and i[0] <= out[-1][1]:  # 当前区间起始位置小于out最后一个元素的结束位置，这时就要进行合并
            out[-1][1] = max(out[-1][1], i[1])  # 合并区间。区间的结束位置 = max(当前遍历区间的结束位置，out最后一个区间的结束位置)
        else:
            out.append(i)  # 不需要合并时的处理。
    return out


# 将输入的字符串转换成区间形式放到intervals数组中。
intervals = []
for i in input().split():  # 切成"1,3"、"2,5"这种形式
    start, end = i.split(",")
    intervals.append([int(start), int(end)])

# 调用合并区间算法
out = merge(intervals)

# 输出处理。
res = ""
for i in out:
    res = res + str(i[0]) + "," + str(i[1]) + " "
print(res.rstrip(";"))

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main( )
{
    int a, b;
    char sep;
    vector<pair<int, int> > intervalArr;
    while( cin>>a>>sep>>b)
        intervalArr.push_back({a,b} );
    sort(intervalArr.begin( ), intervalArr.end( ));

    int i = 0;
    //每次将合并了的区间erase.
    /* 可以合并区间：1. [1,3]和[2,5]
     * 2. [1,5]和 [2,4] 两种情况*/
    while( i+1 < intervalArr.size( )){
        if( intervalArr[i].second >=intervalArr[i+1].first
                || intervalArr[i].first == intervalArr[i+1].first)
        {      
            intervalArr[i].second = max(intervalArr[i].second, intervalArr[i+1].second);
            intervalArr.erase(intervalArr.begin()+i+1);
        }else
            ++i;
    }
    int len = intervalArr.size( );
    for(int i =0; i< len-1; ++i)
        cout<<intervalArr[i].first<<sep<<intervalArr[i].second<<" ";
    cout<<intervalArr[len-1].first<<sep<<intervalArr[len-1].second<<endl;
    return 0;
}

import java.util.*;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String in = sc.nextLine();
        String[] inPairs = in.split(" ");
        ArrayList<Pair> pairs = new ArrayList<>();
        for (String inPair : inPairs) {
            int[] pairInt = Arrays.stream(inPair.split(",")).mapToInt(Integer::valueOf).toArray();
            pairs.add(new Pair(pairInt[0], pairInt[1]));
        }
        ArrayList<Pair> result = new ArrayList<>();
        int n = pairs.size();
        Collections.sort(pairs);
        if (n == 0) { return; }
        Pair ps = pairs.get(0);
        for (int i=1; i<n; i++) {
            Pair cur = pairs.get(i);
            if (ps.end >= cur.begin) {
                ps.end = Math.max(ps.end, cur.end);
            }
            else {
                result.add(ps);
                ps = cur;
            }
        }
        result.add(ps);
        for (Pair p : result) {
            System.out.printf("%d,%d ",p.begin, p.end);
        }
    }
}


class Pair implements Comparable<Pair>{
    public int begin, end;
    public Pair(int begin, int end) {
        this.begin = begin;
        this.end = end;
    }
    public Pair() {}

    @Override
    public int compareTo(Pair p) {
        return Comparator.comparing((Pair pair) ->pair.begin).thenComparing((Pair pair) ->pair.end).compare(this, p);
    }
}

import java.util.*;
public class Main {
    // 合并区间
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] ss = in.nextLine().split(" ");
        int[][] arr = new int[ss.length][2];
        for (int i = 0; i < ss.length; i++) {
            String[] tmp = ss[i].split(",");
            arr[i][0] = Integer.parseInt(tmp[0]);
            arr[i][1] = Integer.parseInt(tmp[1]);
        }
        Arrays.sort(arr, (a, b)->a[0]-b[0]);
        int start = arr[0][0], end = arr[0][1];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i][0] <= end) { // 有交
                end = Math.max(end, arr[i][1]);
            } else { // 不交
                System.out.print(start + "," + end + " ");
                start = arr[i][0];
                end = arr[i][1];
            }
        }
        System.out.println(start + ","+ end);
    }
}

import sys

line = raw_input().strip().split()
inters = [map(int, x.split(',')) for x in line]
inters = sorted(inters)

cur = inters[0]
r = []
for inter in inters[1:]:
    if cur[1] < inter[0]:
        r.append(cur)
        cur = inter
    else:
        cur[1] = max(cur[1], inter[1])
r.append(cur)

print ' '.join([','.join(map(str, x)) for x in r])

#include <bits/stdc++.h>

using namespace std;

struct NODE{
    int l, r;
    NODE():l(), r(){}
    NODE(int x, int y):l(x), r(y){}
};
bool cmp(NODE x, NODE y){
    if(x.l==y.l) return x.r<y.r;
    return x.l<y.l;
}
int main(){
    int x, y, j;
    vector<NODE>vec, ans;
    while(~scanf("%d,%d", &x, &y)){
        vec.push_back(NODE(x, y));
    }
    sort(vec.begin(), vec.end(), cmp);
    for(int i=0; i<vec.size(); ){
        x = vec[i].l, y=vec[i].r;
        int mx = y;
        for(j=i+1; j<vec.size(); j++){
            if(vec[j].l<=mx){//可以合并
               mx=max(mx, vec[j].r);
            }else{
                ans.push_back(NODE(x, mx));
                i=j;break;
            }
        }
        if(j==vec.size()) ans.push_back(NODE(x, mx)), i=j;
    }
    for(int i=0; i<ans.size(); i++) printf("%d,%d%c", ans[i].l, ans[i].r, i==(ans.size()-1)?'\n':' ');
    return 0;
}

2022更新C++

参考剑指 Offer II 074. 合并区间，这里面的题解还是有意思的

头条又一个类似经历

关键：排序，如何比较，如何更新

todo:更新之前C方法，优化JAVA compare方法

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main( )
{
    int a, b;
    char sep;
    vector<vector<int> > source , ret;
    while( cin>>a>>sep>>b)
        source.push_back({a,b} );
    sort(source.begin(),source.end());
    
    int left , right;
    
    for(int i =0 ; i< source.size(); i++){
        left = source[i][0], right = source[i][1];
        if( ret.size()==0 || ret.back()[1] < left){
            ret.push_back( source[i]);//{left,right}
        }else{
            //右边界容易错哈
            //source[i][1] = max( ret.back()[1] , right);//这条浪费5分站
            ret.back()[1] = max( ret.back()[1] , right);
        }
    }
    
    for(int j=0; j<ret.size();j++){
        cout<<ret[j][0]<<","<<ret[j][1];
        if(j-1 - ret.size() !=0){
            cout<<" ";
        }
    }
    
    return 0;
    
}

2020框架
    //skeleton
    public void skelenton(){
        //3.1 get sequence input 基础功
        //3.1a split and save to object Array

        //3.2 sort the objects using DIY-sort

        //3.3 compara neibough zone ,if the are merged , update current-coupole -upper ,
        //&nbs***bsp;else Print the current couple , then update the current position;

    }

import java.io.*;
import java.util.*;


class Zone{
    int from;
    int to;

    public Zone(int from, int to) {
        this.from = from;
        this.to = to;
    }
}

public class IntervalMerge {


    public static void main(String [] args) throws IOException {


        //3.1 input
        //这个需要再次熟悉哈
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().split(" ");

        //3.1a to object array
        Zone [] zones = new Zone[strs.length];
        int index =0;
        for(String st: strs){
            String[] mins = st.split(",");

            //务必把class 声明放到启动类外面，放在内部类,static 是不能识别
            zones[index++] = new Zone(Integer.valueOf(mins[0]), Integer.valueOf(mins[1]));
            //new Zone(Integer.parseInt(mins[0]), Integer.parseInt(mins[1]));
        }
        //3.2 sort

        Arrays.sort(zones, new Comparator<Zone>() {
            @Override
            public int compare(Zone o1, Zone o2) {

                //change
                return o1.from - o2.from;
            }
        });



        //3.3 major  update zone

        int HaoJiYouStart = 0;

        //start not 0 ,but 1
        for(int i = 1 ;i < strs.length; i++){

            //new start is less
            if( zones[i].from   <=   zones[ HaoJiYouStart ].to){


                //update haoJIyou
                zones[ HaoJiYouStart ].to = Math.max(zones[i].to,zones[HaoJiYouStart].to); //新的尾巴


            }else{
                //first print ,then update
                System.out.print(zones[HaoJiYouStart].from+","+zones[HaoJiYouStart].to+" ");
                HaoJiYouStart = i; //use new start;
            }

        }
        // 因为 最后一个元素 肯定会走第一个逻辑判定
        System.out.println(zones[HaoJiYouStart].from+","+zones[HaoJiYouStart].to);


    }




}

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

class Node{
	public int start;
	public int end;
	public Node(int start, int end) {
		this.start = start;
		this.end = end;
	}
}
public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String string = scanner.nextLine();
		String[] strings = string.split(" ");
		Node[] node = new Node[strings.length];
		for(int i = 0; i < strings.length; i++) {
			String[] strings2 = strings[i].split(",");
			node[i] = new Node(Integer.valueOf(strings2[0]), Integer.valueOf(strings2[1]));
		}
		Arrays.sort(node, new Comparator<Node>() {
			public int compare(Node o1, Node o2) {
				return o1.start - o2.start;
			}
		});
		int cur = 0;
		for(int i = 1; i < node.length; i++) {
			if(node[i].start <= node[cur].end) {
				node[cur].end = Math.max(node[i].end, node[cur].end);
			}
			else {
				System.out.print(node[cur].start + "," + node[cur].end + " ");
				cur = i;
			}
		}
		System.out.println(node[cur].start + "," + node[cur].end);
	}
}

//贡献一个AC的cpp，具体思路写在注释里了
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
struct node{
    int a;
    int b;
};
bool cmp(node &x,node &y){
    return x.b<y.b;
}
int main(){
    char m;
    int a,b;
    vector<node>data;
    while(cin>>a>>m>>b){
        node tmp;
        tmp.a=a;
        tmp.b=b;
        data.push_back(tmp);
    }
    sort(data.begin(),data.end(),cmp);
    vector<int>ans;
    int n=data.size();
    bool can=true;
    for(int i=n-1;i>0;i--){
        if(data[i].a<=data[i-1].b){//可以合并
            data[i-1].b=data[i].b;
            //如果后一个区间的左端点小于前一个区间的左端点，将前一个置为后一个左端点
            if(data[i].a<=data[i-1].a) 
                data[i-1].a=data[i].a;
        }
        else{   //不能合并
            ans.push_back(data[i].a);
            ans.push_back(data[i].b);
        }
    }
    ans.push_back(data[0].a);  //不管第一个能不能被合并，都得放进结果中
    ans.push_back(data[0].b);
    //cout<<ans.size();
    for(int i=ans.size()-1;i>=1;i-=2){
        cout<<ans[i-1]<<","<<ans[i]<<" ";
    }
    return 0;
}

c++11版

#include <iostream>
#include <sstream>
#include <algorithm>
using namespace std;

int main() {     string line;     getline(cin, line);     stringstream ss(line);     string gap;     vector<pair<int,int>> interval;      while( ss >> gap) {         auto fn = [&]() {             auto pos = gap.find(',');             const int val1 = stoi(string(gap.begin(), gap.begin()+pos));             const int val2 = stoi(string(gap.begin()+pos+1, gap.end()));             return make_pair(val1, val2);         };         interval.push_back(fn());     }          auto fn = [&](pair<int,int>& a, pair<int,int>& b) {         return a.first < b.first;     };     sort(interval.begin(), interval.end(), fn);          vector<pair<int,int>> ans;     ans.push_back(interval.front());     for(int i = 1; i < interval.size(); ++i) {         if(interval[i].first <= ans.back().second) {             ans.back().second = max(ans.back().second, interval[i].second);         }         else             ans.push_back(interval[i]);     }          for(int i = 0; i < ans.size(); ++i) {         cout << ans[i].first << "," << ans[i].second;         i == ans.size()-1 ? cout << endl : cout << " ";     }
}