Интервалы перекрытия слияния

Question

Вопрос: Учитывая набор временных интервалов в любом порядке, объедините все перекрывающиеся интервалы в один и выведите результат, который должен иметь только взаимно исключающие интервалы. Пусть интервалы представлены как пары целых чисел для простоты. Например, пусть заданный набор интервалов {{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 

Answer 1

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 метод i Nside в public class Ideone
• Interval и IntervalComparator являются только внутренние классы

Выход:

1 6 
8 10 
15 20 

Answer 2

Вот ваш утонченный код:

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

И имя это Java-файл "Ideone.java"

Answer 3

Я предпочел бы поставить метод слияния, как это:

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

Answer 4

Моя реализация с использованием 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; 
    } 
}