Задача о покрытии отрезка

Задача в общем виде формулируется так: По данным n отрезкам необходимо найти множество точек минимального размера, для которого каждый из отрезков содержит хотя бы одну из точек.
Вполне понятно, что достаточно рассматривать только правые концы каждого из отрезков, но вот этот факт я использовать никак и не могу( Мое решение, на данный момент, заключается вот в чем:
Я считываю эти n отрезков(сами по себе они хранятся в массиве), беру правый конец каждого из них в отдельный массив Далее задаю простое условие о принадлежности правого конца некоторого отрезка другим отрезкам, которые есть; если условие выполнено - в еще одном массиве кладу в соответствующий индекс инкремент. В результате я получаю правые точки и то, скольким еще отрезкам они принадлежат, однако это совсем не приближает меня к решению, ибо полученной информации недостаточно.
Помогите молодому разобраться в проблеме, как ее исправить и вообще в каком направлении думать. Понимаю, что решение детское привел, но надеюсь на help) при необходимости, код добавлю=)
public static void main(String [] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt();
int[] array = new int[2 * n]; ArrayList right_bounds = new ArrayList();
for (int i = 0; i < array.length; i += 2) { int a = sc.nextInt(); int b = sc.nextInt(); right_bounds.add(b); array[i] = a; array[i + 1] = b; } int[] right_bounds_count = new int[right_bounds.size()]; Arrays.fill(right_bounds_count, 0); for (int i = 0; i < array.length; i += 2) { for (int j = 0; j < right_bounds.size(); j++) { if (right_bounds.get(j) >= array[i] && right_bounds.get(j) <= array[i + 1]) right_bounds_count[j]++; } }
}

Ответ

Вот решение:
public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[][] data = new int[n][]; int i = 0; while (scanner.hasNext()) { int a = scanner.nextInt(); int b = scanner.nextInt(); data[i++] = new int[]{a,b}; } Arrays.sort(data,(o1, o2) -> { int v = o1[1] - o2[1]; return v != 0 ? v : o1[0] - o2[0]; }); //System.out.println(Arrays.deepToString(data)); String[] res = cover(data); System.out.println(res.length); for (int j = 0; j < res.length; j++) { System.out.print(res[j] + " "); } }
public static String[] cover(int[][] arr){ StringBuilder sb = new StringBuilder(); for (int i = 0, l = arr.length; i < l ; i++ ) { int point = arr[i][1]; for (int j = i ; j < l && point <= arr[j][1] && point >= arr[j][0] ; j++) { i = j; } sb.append(point).append(" ");
} return sb.toString().split(" "); }
Возьмём все точки-концы отрезков (как левые, так и правые) и отсортируем их. При этом для каждой точки сохраним вместе с ней номер отрезка, а также то, каким концом его она является (левым или правым). Кроме того, отсортируем точки таким образом, что, если есть несколько точек с одной координатой, то сначала будут идти левые концы, и только потом - правые. Заведём стек, в котором будут храниться номера отрезков, рассматриваемых в данный момент; изначально стек пуст. Будем двигаться по точкам в отсортированном порядке. Если текущая точка - левый конец, то просто добавляем номер её отрезка в стек. Если же она является правым концом, то проверяем, не был ли покрыт этот отрезок (для этого можно просто завести массив булевых переменных). Если он уже был покрыт, то ничего не делаем и переходим к следующей точке (забегая вперёд, мы утверждаем, что в этом случае в стеке текущего отрезка уже нет). Если же он ещё не был покрыт, то мы добавляем текущую точку в ответ, и теперь мы хотим отметить для всех текущих отрезков, что они становятся покрытыми. Поскольку в стеке как раз хранятся номера непокрытых ещё отрезков, то будем доставать из стека по одному отрезку и отмечать, что он уже покрыт, пока стек полностью не опустеет. По окончании работы алгоритма все отрезки будут покрыты, и притом наименьшим числом точек (повторимся, здесь важно требование, что при равенстве координат сначала идут левые концы, и только затем правые).