Описание задачи

По данным n отрезкам необходимо найти множество точек минимального размера, для которого каждый из отрезков содержит хотя бы одну из точек. В первой строке дано число 1≤n≤100 отрезков. Каждая из последующих nn строк содержит по два числа 0≤l≤r≤10^9, задающих начало и конец отрезка. Выведите оптимальное число m точек и сами m точек. Если таких множеств точек несколько, выведите любое из них.

Надежный шаг

Надежным шагом является выбор правой точки отрезка который ближе всех к началу с последующим удалением всех отрезков которые точка захватила

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

/**
 * Main
 *
 * @author Vladislav Sidlyarevich <vlsidlyarevich@gmail.com>
 * Created on 3/7/21.
 */
public class Main {

    private List<Point> points = new ArrayList<>();

  
    public void run() {
        Scanner scanner = new Scanner(System.in).useDelimiter("\n");
        ;
        int n = Integer.parseInt(scanner.nextLine());

        for (int i = 0; i < n; i++) {
            String[] coordinates = scanner.nextLine().split("\\s+");
            points.add(new Point(Long.parseLong(coordinates[0]), Long.parseLong(coordinates[1])));
        }

        scanner.close();
        List<Long> result = calculate();
        System.out.println(result.size());
        System.out.println(calculate().stream().map(String::valueOf)
                .reduce("", (i, x) -> i + " " + x)
                .trim());
    }

    private List<Long> calculate() {
        //Отсортировать отрезки так, чтобы отрезки начинающиеся раньше стояли первыми
        Collections.sort(points);

        List<Long> result = new ArrayList<>();
        result.add(points.get(0).end);

        //Идти по списку c возможностью удаления

        for (Point point : points) {
            long start = point.start;
            long end = point.end;

            if (result.contains(end)) {
                continue;
            }

            if (result.get(result.size() - 1) >= start
                    && result.get((result.size() - 1)) <= end) continue;

            result.add(end);
        }

        return result;
    }

    public static void main(String[] args) {
        Main main = new Main();
        main.run();
    }

    private class Point implements Comparable<Point> {
        long start;
        long end;

        public Point(final long start, final long end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(final Point o) {
            if (this.end == o.end) {
                if (this.start < o.start) return -1;
                else if (this.start > o.start) return 1;

                return 0;
            }
            return this.end < o.end ? -1 : 1;
        }
    }
}