56. Merge Intervals

区间合并，先将input根据start的大小进行排序，比较下一个start和前一个end的值的大小，如果下一个start比较大，那么就需要重新记下end的最大值。反之，加入新的Interval。还需要注意一下Scanner的写法。

测试用例:

// 1
4
1,3
2,6
8,10
15,18

// 2
3
1,10;32,45
78,94;5,16
80,100;200,220;16,32

import java.util.*;

class Interval {
    int start;
    int end;

    public Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

class MergeInterval {
    public static void main(String[] args) {
        List<Interval> res = new ArrayList<>();
        Scanner sc = new Scanner(System.in);
        int num = Integer.parseInt(sc.nextLine());
        for (int i = 0; i < num; i++) {
            String[] line = sc.nextLine().split(";");

            for (int j = 0; j < line.length; j++) {
                String[] unit = line[j].split(",");
                System.out.println(Arrays.toString(line));
                System.out.println(Arrays.toString(unit));
                res.add(new Interval(Integer.parseInt(unit[0]), Integer.parseInt(unit[1])));
            }
        }

        List<Interval> result = merge(res);
        for (Interval i : result) {
            System.out.println(i.start + " " + i.end);
        }
    }

    public static List<Interval> merge(List<Interval> intervals) {
        if (intervals.size() <= 1) {
            return intervals;
        }

        List<Interval> res = new LinkedList<>();
        Comparator<Interval> c = new Comparator<>() {
            @Override
            public int compare(Interval i1, Interval i2) {
                return Integer.compare(i1.start, i2.start);
            }
        };
        // Comparator<Interval> c = (i1, i2) -> Integer.compare(i1.start, i2.start);

        intervals.sort(c);

        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        for (Interval i : intervals) {
            if (i.start <= end) {
                end = Math.max(end, i.end);
            } else {
                res.add(new Interval(start, end));
                start = i.start;
                end = i.end;
            }
        }
        res.add(new Interval(start, end));
        return res;
    }
}