合并重叠间隔
问题：给定任何顺序的一组时间间隔，将所有重叠间隔合并为一，并输出应该只有互斥间隔的结果。 为简单起见，将间隔表示为整数对。 例如，让给定的区间集合为{{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 merge(ArrayList 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 result = new ArrayList(); 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 x = new ArrayList(); 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 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 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 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 merge(ArrayList 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 result = new ArrayList (); 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 { public int compare(Interval i1, Interval i2) { return i1.getStart() - i2.getStart(); } }
-
main方法在public class Ideone -
Interval和IntervalComparator只是内部类
输出：
1 6 8 10 15 20
这是您精炼的代码：
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; } } public class Ideone { public static void main(String[] args) throws java.lang.Exception { ArrayList x = new ArrayList (); 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 r = merge(x); for (Interval i : r) { System.out.println(i.start + " " + i.end); } } public static ArrayList merge(ArrayList 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 result = new ArrayList (); 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; } }
并将此java文件命名为“Ideone.java”
我使用BST实现。 要合并的O（logn）：Inorder遍历为您提供更新的间隔。
private static Interval add(Interval root, Interval x){ if(root == null) return x; if(root.start >= x.start){ root.left = add(root.left,x); if(mergeLeft(root,root.left)){ root.left = null; } } else{ root.right = add(root.right,x); if(mergeRight(root,root.right)){ root.right = null; } } return root; } private static boolean mergeLeft(Interval root,Interval left){ if(left.end < root.start) return false; else{ root.start = Math.min(root.start, left.start); root.end = Math.max(root.end, left.end); return true; } } private static boolean mergeRight(Interval root,Interval right){ if(right.start > root.end) return false; else{ root.start = Math.min(root.start, right.start); root.end = Math.max(root.end, right.end); return true; } }
我宁愿把这样的合并方法：
static List merge(List iList) { Collections.sort(iList, new Comparator () { @Override public int compare(Interval o1, Interval o2) { return o1.startTime - o2.startTime; } }); Interval prevIntvl = iList.get(0); List res = new ArrayList<>(); for (int i = 1; i < iList.size(); i++) { Interval curIntvl = iList.get(i); if (curIntvl.startTime < prevIntvl.endTime) { prevIntvl.setEndTime(prevIntvl.endTime > curIntvl.endTime ? prevIntvl.endTime : curIntvl.endTime); } else { res.add(prevIntvl); prevIntvl = curIntvl; } } res.add(prevIntvl); return res; }