合并重叠间隔

Question

问题:给定任意顺序的一组时间间隔,将所有重叠间隔合并为一,并输出应该只具有互斥间隔的结果.为简单起见,将间隔表示为整数对.例如,让给定的一组区间为{{1,3},{2,4},{5,7},{6,8}}.区间{1,3}和{2,4}彼此重叠,因此它们应合并成{1,4}.类似地,{5,7}和{6,8}应该合并并成为{5,8}

编写一个函数,为给定的一组区间产生一组合并区间.

我的代码:

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

class Interval 
{
    int start;
    int end;

    Interval() {
        start = 0;
        end = 0;
    }

    Interval(int s, int e) 
    {
        start = s;
        end = e;
    }
}

class Ideone
{
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {

        if(intervals.size() == 0)
            return intervals;
        if(intervals.size() == 1)
            return intervals;

        Collections.sort(intervals, new IntervalComparator());

        Interval first = intervals.get(0);
        int start = first.start;
        int end = first.end;

        ArrayList<Interval> result = new ArrayList<Interval>();

        for(int i = 1; i < intervals.size(); i++){
            Interval current = intervals.get(i);
            if(current.start <= end){
                end = Math.max(current.end, end);
            }else{
                result.add(new Interval(start, end));
                start = current.start;
                end = current.end;
            }

        }

        result.add(new Interval(start, end));

        return result;

    }
}

class IntervalComparator implements Comparator
{
    public int compare(Object o1, Object o2)
    {
        Interval i1 = (Interval)o1;
        Interval i2 = (Interval)o2;
        return i1.start - i2.start;
    }
}
public static void main (String[] args) throws java.lang.Exception
{
    ArrayList<Interval> x = new ArrayList<Interval>();
    Interval i1 = new Interval(1,3);
    Interval i2 = new Interval(2,6);
    Interval i3 = new Interval(8,10);
    Interval i4 = new Interval(15,18);

    x.add(i1);x.add(i2);x.add(i3);x.add(i4);

    ArrayList<Interval> r = merge(x);

    for(Interval i : r)
    {
        System.out.println(i.start+" "+i.end);
    }

}
}

这些是我编译后得到的错误,有人可以解释一下如何纠正它吗？

Main.java:69: error: class, interface, or enum expected
public static void main (String[] args) throws java.lang.Exception
              ^
Main.java:72: error: class, interface, or enum expected
    Interval i1 = new Interval(1,3);
    ^
Main.java:73: error: class, interface, or enum expected
    Interval i2 = new Interval(2,6);
    ^
Main.java:74: error: class, interface, or enum expected
    Interval i3 = new Interval(8,10);
    ^
Main.java:75: error: class, interface, or enum expected
    Interval i4 = new Interval(15,18);
    ^
Main.java:77: error: class, interface, or enum expected
    x.add(i1);x.add(i2);x.add(i3);x.add(i4);
    ^
Main.java:77: error: class, interface, or enum expected
    x.add(i1);x.add(i2);x.add(i3);x.add(i4);
              ^
Main.java:77: error: class, interface, or enum expected
    x.add(i1);x.add(i2);x.add(i3);x.add(i4);
                        ^
Main.java:77: error: class, interface, or enum expected
    x.add(i1);x.add(i2);x.add(i3);x.add(i4);
                                  ^
Main.java:79: error: class, interface, or enum expected
        ArrayList<Interval> r = merge(x);
        ^
Main.java:81: error: class, interface, or enum expected
        for(Interval i : r)
        ^
Main.java:84: error: class, interface, or enum expected
        }
        ^
12 errors

Answer 1

Ideone.java:

import java.util.*;

public class Ideone
{   
    public static void main (String[] args) throws java.lang.Exception
    {
        ArrayList<Interval> x = new ArrayList<>();

        x.add(new Interval(1, 3));
        x.add(new Interval(2, 6));
        x.add(new Interval(8, 10));
        x.add(new Interval(15, 18));
        x.add(new Interval(17, 20));

        x = merge(x);

        for(Interval i : x)
        {
            System.out.println(i.getStart() + " " + i.getEnd());
        }
    }

    public static ArrayList<Interval> merge(ArrayList<Interval> intervals) {

        if(intervals.size() == 0 || intervals.size() == 1)
            return intervals;

        Collections.sort(intervals, new IntervalComparator());

        Interval first = intervals.get(0);
        int start = first.getStart();
        int end = first.getEnd();

        ArrayList<Interval> result = new ArrayList<Interval>();

        for (int i = 1; i < intervals.size(); i++) {
            Interval current = intervals.get(i);
            if (current.getStart() <= end) {
                end = Math.max(current.getEnd(), end);
            } else {
                result.add(new Interval(start, end));
                start = current.getStart();
                end = current.getEnd();
            }
        }

        result.add(new Interval(start, end));
        return result;
    }
}

class Interval 
{
    private int start;
    private int end;

    Interval() {
        start = 0;
        end = 0;
    }

    Interval(int s, int e) 
    {
        start = s;
        end = e;
    }

    public int getStart() {
        return start;
    }

    public int getEnd() {
        return end;
    }
}

class IntervalComparator implements Comparator<Interval>
{
    public int compare(Interval i1, Interval i2)
    {
        return i1.getStart() - i2.getStart();
    }
}

• main 方法在里面 public class Ideone
• Interval而且IntervalComparator只是内部阶级

输出:

1 6
8 10
15 20