fork download
copy 
  1. import java.util.ArrayList;
  2. import java.util.Collections;
  3. import java.util.List;
  4.  
  5. /**
  6.  * @author Victor Williams Stafusa da Silva
  7.  */
  8. public class Main {
  9.     public static void main(String[] args) {
  10.         System.out.println(Intervalo.reduzir(new Intervalo(1, 3), new Intervalo(2, 6), new Intervalo(7, 10)));
  11.         System.out.println(Intervalo.reduzir(new Intervalo(1, 3), new Intervalo(2, 8), new Intervalo(7, 10)));
  12.         System.out.println(Intervalo.reduzir(new Intervalo(1, 3), new Intervalo(4, 7), new Intervalo(8, 10)));
  13.         System.out.println(Intervalo.reduzir(new Intervalo(1, 3), new Intervalo(3, 10)));
  14.     }
  15. }
  16.  
  17. final class Intervalo {
  18.     private final double a;
  19.     private final double b;
  20.  
  21.     public Intervalo(double a, double b) {
  22.         if (b < a) throw new IllegalArgumentException();
  23.         this.a = a;
  24.         this.b = b;
  25.     }
  26.  
  27.     public double getA() {
  28.        return a;
  29.     }
  30.  
  31.     public double getB() {
  32.        return b;
  33.     }
  34.  
  35.     @Override
  36.     public String toString() {
  37.         return "[" + a + "<->" + b + "]";
  38.     }
  39.  
  40.     public Evento getEventoA() {
  41.         return new Evento(true, a);
  42.     }
  43.  
  44.     public Evento getEventoB() {
  45.         return new Evento(false, b);
  46.     }
  47.  
  48.     @SafeVarargs
  49.     public static List<Intervalo> reduzir(Intervalo... lista) {
  50.         return reduzir(List.of(lista));
  51.     }
  52.  
  53.     public static List<Intervalo> reduzir(List<Intervalo> lista) {
  54.         List<Evento> eventos = new ArrayList<>(lista.size() * 2);
  55.         for (Intervalo i : lista) {
  56.             eventos.add(i.getEventoA());
  57.             eventos.add(i.getEventoB());
  58.         }
  59.         Collections.sort(eventos);
  60.         List<Intervalo> saida = new ArrayList<>(lista.size());
  61.         int contagem = 0;
  62.         double inicio = Double.NEGATIVE_INFINITY;
  63.         for (Evento e : eventos) {
  64.             if (e.isInicioIntervalo()) {
  65.                 if (contagem == 0) inicio = e.getPonto();
  66.                 contagem++;
  67.             } else {
  68.                 contagem--;
  69.                 if (contagem == 0) saida.add(new Intervalo(inicio, e.getPonto()));
  70.             }
  71.         }
  72.         return saida;
  73.     }
  74. }
  75.  
  76. final class Evento implements Comparable<Evento> {
  77.     private final boolean inicioIntervalo;
  78.     private final double ponto;
  79.  
  80.     public Evento(boolean inicioIntervalo, double ponto) {
  81.         this.inicioIntervalo = inicioIntervalo;
  82.         this.ponto = ponto;
  83.     }
  84.  
  85.     public boolean isInicioIntervalo() {
  86.         return inicioIntervalo;
  87.     }
  88.  
  89.     public double getPonto() {
  90.         return ponto;
  91.     }
  92.  
  93.     @Override
  94.     public int compareTo(Evento outro) {
  95.         return this.ponto < outro.ponto ? -1
  96.                 : this.ponto > outro.ponto ? 1
  97.                 : this.inicioIntervalo == outro.inicioIntervalo ? 0
  98.                 : this.inicioIntervalo ? -1
  99.                 : 1;
  100.     }
  101. }
Success #stdin #stdout 0.12s 37724KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[[1.0<->6.0], [7.0<->10.0]]
[[1.0<->10.0]]
[[1.0<->3.0], [4.0<->7.0], [8.0<->10.0]]
[[1.0<->10.0]]
https://ideone.com/GbmcB5
language:
Java (HotSpot 12)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!