合并重叠间隔 [英] Merge Overlapping Intervals

问题描述

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

Question : Given a set of time intervals in any order, merge all overlapping intervals into one and output the result which should have only mutually exclusive intervals. Let the intervals be represented as pairs of integers for simplicity. For example, let the given set of intervals be {{1,3}, {2,4}, {5,7}, {6,8} }. The intervals {1,3} and {2,4} overlap with each other, so they should be merged and become {1, 4}. Similarly {5, 7} and {6, 8} should be merged and become {5, 8}

编写一个函数，该函数为给定间隔集生成合并间隔集.

Write a function which produces the set of merged intervals for the given set of intervals.

我的代码:

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);
    }

}
}

这些是我编译后得到的错误，任何人都可以向我解释如何纠正它吗?

These are the errors which i got after compiling, can anyone please explain me how to rectify it?

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

推荐答案

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只是内部类
• main method is inside the public class Ideone
• Interval and IntervalComparator are just inner classes

输出:

1 6
8 10
15 20

这篇关于合并重叠间隔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！