Stepik - 4.1. Задача о расписании
Описание задачи
По данным 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;
}
}
}