java 合并重叠区间
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/31670849/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
提示：将鼠标放在中文语句上可以显示对应的英文。显示中英文
时间：2020-11-02 18:58:25 来源:igfitidea点击:
Merge Overlapping Intervals
提问by coder101
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}
问题：给定一组任意顺序的时间间隔，将所有重叠的间隔合并为一个，并输出应该只有互斥间隔的结果。为简单起见，将区间表示为整数对。例如，让给定的一组区间为 {{1,3}, {2,4}, {5,7}, {6,8} }。区间{1,3}和{2,4}相互重叠，所以应该合并成{1, 4}。同样 {5, 7} 和 {6, 8} 应该合并成为 {5, 8}
Write a function which produces the set of merged intervals for the given set of intervals.
编写一个函数，为给定的一组区间生成一组合并的区间。
My code:
我的代码：
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
采纳答案by almightyGOSU
Ideone.java:
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();
}
}
mainmethod is inside thepublic class IdeoneIntervalandIntervalComparatorare just inner classes
main方法在里面public class IdeoneInterval并且IntervalComparator只是内部类
Output:
输出：
1 6
8 10
15 20
回答by Yurii
Here is your refined code:
这是您的改进代码：
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<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);
}
}
public static 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;
}
}
And name this java file "Ideone.java"
并将这个java文件命名为“Ideone.java”
回答by Jay
My implementation using BST. O(logn) to merge: Inorder traversal gives you updated intervals.
我使用 BST 的实现。O(logn) 合并：中序遍历为您提供更新的间隔。
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;
}
}
回答by Alexandru Ionescu
class Solution {
public List<Interval> merge(List<Interval> intervals) {
if (intervals.size() <= 1) {
return intervals;
}
intervals.sort((i1, i2) -> Integer.compare(i1.start, i2.start));
List<Interval> result = new LinkedList<Interval>();
int start = intervals.get(0).start;
int end = intervals.get(0).end;
for(Interval interval : intervals) {
if (interval.start <= end) {
end = Math.max(end, interval.end);
}
else {
result.add(new Interval(start, end));
start = interval.start;
end = interval.end;
}
}
result.add(new Interval(start, end));
return result;
}
}
回答by RIPAN
I would rather put the merge method like this:
我宁愿像这样放置合并方法：
static List<Interval> merge(List<Interval> iList) {
Collections.sort(iList, new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
return o1.startTime - o2.startTime;
}
});
Interval prevIntvl = iList.get(0);
List<Interval> 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;
}
