Как решить задачу о перекрытии отрезков за O(n*log(n)) c помощью stream api java, если есть решение старыми средствами?

Похоже бесперспективно переписывать любой код средствами Java 8 stream api, если важен порядок перебора элементов. Сами потоки хорошо подходят для применения однотипной операции ко всем элементам. Там где нужно сравнивать один элемент, с другим элементом массива, потоки не подходят, потому как они не поддерживают операцию next(); Так что по состоянию на 2021 год, наверное нужно оставлять в этом участке кода итераторы.

Задачу можно решить за O(nlogn). Задачу можно решить потоками. Решение сложное так как опирается на заметание.

Кли предложил заметание для решения задачи названной его именем: Klee's measure problem. На русском: поиск длины объединения отрезков на прямой.

Заметание - общая технология. У вас есть упорядоченная очередь событий, обрабатывая события вы обновляете состояние (статус). В зависимости от изменения состояния вы печатаете (выводите) результат. Алгоритм потоковый: события считываются из потока и результаты выводятся в другой поток. В сложных случаях несколько заметаний могут быть объеденены в конвейер.

Ниже решаем такую задачу: нужно удалить те части зелёных отрезков, которые покрыты синими. Это не вся задача из вопроса, но самая сложная её часть. Когда это сделано останется в результат подмешать синие отрезки.

В нашей задаче событием будет конец отрезка. Событие характеризуется координатой, типом конца (начало или конец), признаком включена или нет сама точка события в отрезок (полуинтервал, интервал), цветом (зеленый или синий).

Например зелёный отрезок [0, 10] породит два зелёных события, которые можно изобразить так:

0         10
01234567890123
[         ]

Для синих отрезков автор вопроса предлагает нотацию [5, 6] которая сбивает с толку. Преобразуем синие отрезки: [5, 6] -> (4, 7) - отрезок расширен, а концы его исключены. Событиями будут точки 4 и 7:

0         10
01234567890123
    (  )

Зелёный [0, 10] и синий [5, 6] вместе:

0         10
01234567890123
[   (  )  ]

Состояние будет состоять из двух битов: бит g означает "в зеленом отрезке", бит b - "внутри синего" (в этой фразе "в" и "внутри" - разные вещи!). Последняя строка "зелёный без синего":

0         10
01234567890123
[   (  )  ]
-----------   g        покрыто зелёным отрезком
     --       b        покрыто синим интервалом
-----  ----   g & ~b   зелёный, но не синий

Распишем события и состояния для последней картинки:

 x e g b g&~b комментарий
     0 0 0
 0 [ 1 0 1    переход g&~b 0->1: печатаем '0['
 4 ( 1 1 0    переход g&~b 1->0: печатаем '4]'
 7 ) 1 0 1    переход g&~b 0->1: печатаем '7['
10 ] 0 0 0    переход g&~b 1->0: печатаем '10]'

Итоговая распечатка. Её можно собрать попарно чтобы получить отрезки:

0[, 4], 7[, 10]    ->    [0, 4], [7, 10]

Более сложный пример. Зелёные [0, 3], [5, 8], [10, 13], [18, 20]. Синие [2, 6], [9, 13], [17, 17], [18, 18]. Отратите внимание на два синих отрезка в конце - они пересеклись:

0         10        20
012345678901234567890123456789
[  ] [  ] [  ]    [ ]
 (     )(     ) ( )
                 ( )
---- ---- ----    ---   g
  -----  -----   --     b
--     --          --   g & ~b

События и состояния:

 x e g b g&~b комментарий
     0 0 0
 0 [ 1 0 1    переход g&~b 0->1: печатаем '0['
 1 ( 1 1 0    переход g&~b 1->0: печатаем '1]'
 3 ] 0 1 0
 5 [ 1 1 0
 7 ) 1 0 1    переход g&~b 0->1: печатаем '7['
 8 ] 0 0 0    переход g&~b 1->0: печатаем '8]'
 8 ( 0 1 0
10 [ 1 1 0
13 ] 0 1 0
14 ) 0 0 0
16 ( 0 1 0
17 ( 0 2 0    синие могут пересекаться. b - не бит, а счётчик
18 ) 0 1 0
18 [ 1 1 0
19 ) 1 0 1    переход g&~b 0->1: печатаем '19['
20 ] 0 0 0    переход g&~b 1->0: печатаем '20]'

Печать целиком:

[0, 1], [7, 8], [19, 20]

Таким образом из зелёных отрезков удаляются участки выделеные синими. Полученные отрезки надо смешать с оригинальными (не раздутыми) синими, что даст ответ.

Заметание позволяет за линейное время вычислить любую булеву функцию на совокупностях отрезков (предварительная сортировка добавляет nlogn).

Программа:

import java.util.function.Consumer;
import java.util.function.Function;
import java.util.stream.Stream;

public class SegmentOverlapping {

    public static void main(String... args) {
        test(
            new Segment[] { new Segment(0, 3), new Segment(5, 8), new Segment(10, 13), new Segment(18, 20) },
            new Segment[] { new Segment(2, 6), new Segment(9, 13), new Segment(17, 17), new Segment(18, 18) }
        );
        test(
            new Segment[] { new Segment(0, 10), new Segment(11, 11) },
            new Segment[] { new Segment(5, 6), new Segment(11, 11) }
        );
    }

    private static void test(Segment[] green, Segment[] blue) {
        System.out.println("-");
        printSegments("g", Stream.of(green));
        printSegments("b", Stream.of(blue));
        printSegments("r", maskGreenByBlue(green, blue));
    }

    private static void printSegments(String prefix, Stream<Segment> segments) {
        System.out.print(prefix + ":");
        segments.forEach(s -> System.out.print(" " + s));
        System.out.println();
    }

    private static Stream<Segment> maskGreenByBlue(Segment[] green, Segment[] blue) {
        Stream<Event> masked = maskGreenByBlueEvents(green, blue);

        Stream.Builder<Segment> builder = Stream.builder();

        Stream
        .concat(
            masked,
            makeStream(blue, Color.BLUE, 0)
        )
        .sorted()
        .forEach(new SegmentHandler(builder));

        return builder.build();
    }

    private static Stream<Event> maskGreenByBlueEvents(Segment[] green, Segment[] blue) {
        Stream.Builder<Event> builder = Stream.builder();

        Stream
        .concat(
            makeStream(green, Color.GREEN, 0),
            makeStream(blue, Color.BLUE, 1)
        )
        .sorted()
        .forEach(new BlueMaskHandler(builder));

        return builder.build();
    }

    private static Stream<Event> makeStream(Segment[] segments, Color color, int margin) {
        return Stream
            .of(segments)
            .map(s -> Stream.of(
                new Event(color, Edge.START , s.start  - margin,  margin),
                new Event(color, Edge.FINISH, s.finish + margin, -margin)
            ))
            .flatMap(Function.identity())
        ;
    }
}

class Segment {
    public final int start;
    public final int finish;

    public Segment(int start, int finish) {
        this.start = start;
        this.finish = finish;
    }

    @Override
    public String toString() {
        return "[" + start + ", " + finish + "]";
    }
}

enum Edge { START, FINISH; }

enum Color { GREEN, BLUE; }

class Event implements Comparable<Event> {
    public final Color color;
    public final Edge edge;
    public final int x;
    public final int dx;
    public Event(Color color, Edge edge, int x, int dx) {
        this.color = color;
        this.edge = edge;
        this.x = x;
        this.dx = dx;
    }

    @Override
    public int compareTo(Event other) {
        int cX = Integer.compare(x, other.x);
        if (cX != 0) {
            return cX;
        }
        return Integer.compare(dx, other.dx);
    } 

    @Override
    public String toString() {
        return "" + color + " " + edge + " " + x;
    }
}

class BlueMaskHandler implements Consumer<Event> {
    private final Stream.Builder<Event> builder;
    private int inGreen;
    private int inBlue;

    public BlueMaskHandler(Stream.Builder<Event> builder) {
        this.builder = builder;
        inGreen = 0;
        inBlue = 0;
    }

    @Override
    public void accept(Event event) {
        switch (event.color) {
        case GREEN:
            switch (event.edge) {
            case START:
                if (inGreen == 0 && inBlue == 0) {
                    builder.add(event);
                }
                ++inGreen;
                break;
            case FINISH:
                --inGreen;
                if (inGreen == 0 && inBlue == 0) {
                    builder.add(event);
                }
                break;
            }
            break;
        case BLUE:
            switch (event.edge) {
            case START:
                if (inBlue == 0 && inGreen > 0) {
                    builder.add(new Event(Color.GREEN, Edge.FINISH, event.x, 0));
                }
                ++inBlue;
                break;
            case FINISH:
                --inBlue;
                if (inBlue == 0 && inGreen > 0) {
                    builder.add(new Event(Color.GREEN, Edge.START, event.x, 0));
                }
                break;
            }
            break;
        }
    }
}

class SegmentHandler implements Consumer<Event> {
    private final Stream.Builder<Segment> builder;
    private int start;

    public SegmentHandler(Stream.Builder<Segment> builder) {
        this.builder = builder;
        start = 0;
    }

    @Override
    public void accept(Event event) {
        switch (event.edge) {
        case START:
            start = event.x;
            break;
        case FINISH:
            builder.add(new Segment(start, event.x));
            break;
        }
    }
}

$ javac SegmentOverlapping.java && java SegmentOverlapping 
-
g: [0, 3] [5, 8] [10, 13] [18, 20]
b: [2, 6] [9, 13] [17, 17] [18, 18]
r: [0, 1] [2, 6] [7, 8] [9, 13] [17, 17] [18, 18] [19, 20]
-
g: [0, 10] [11, 11]
b: [5, 6] [11, 11]
r: [0, 4] [5, 6] [7, 10] [11, 11]