问题:给定一组任意时间间隔的时间,将所有重叠的时间间隔合并为一个,然后输出结果,该结果应该只有互斥的时间间隔。为了简单起见,将间隔表示为整数对。例如,让给定的间隔集为{{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