问题:给定一组任意顺序的时间间隔,将所有重叠的间隔合并为一个,并输出应该只有互斥间隔的结果。为简单起见,让间隔表示为整数对。 例如,让给定的间隔集为 {{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
最佳答案
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
关于java - 合并重叠区间,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31670849/