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

#java #алгоритм #геометрия #вычислительная_геометрия

Задача в общем виде формулируется так: По данным 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]++;
            }
        }    

    }

    

Ответы

Ответ 1

Вот решение:

    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(" ");
    }


Возьмём все точки-концы отрезков (как левые, так и правые) и отсортируем их. При
этом для каждой точки сохраним вместе с ней номер отрезка, а также то, каким концом
его она является (левым или правым). Кроме того, отсортируем точки таким образом, что,
если есть несколько точек с одной координатой, то сначала будут идти левые концы, и
только потом - правые. Заведём стек, в котором будут храниться номера отрезков, рассматриваемых
в данный момент; изначально стек пуст. Будем двигаться по точкам в отсортированном
порядке. Если текущая точка - левый конец, то просто добавляем номер её отрезка в стек.
Если же она является правым концом, то проверяем, не был ли покрыт этот отрезок (для
этого можно просто завести массив булевых переменных). Если он уже был покрыт, то ничего
не делаем и переходим к следующей точке (забегая вперёд, мы утверждаем, что в этом
случае в стеке текущего отрезка уже нет). Если же он ещё не был покрыт, то мы добавляем
текущую точку в ответ, и теперь мы хотим отметить для всех текущих отрезков, что они
становятся покрытыми. Поскольку в стеке как раз хранятся номера непокрытых ещё отрезков,
то будем доставать из стека по одному отрезку и отмечать, что он уже покрыт, пока стек
полностью не опустеет. По окончании работы алгоритма все отрезки будут покрыты, и притом
наименьшим числом точек (повторимся, здесь важно требование, что при равенстве координат
сначала идут левые концы, и только затем правые).


Ответ 2

Брать лишь правый конец отрезка - немного не верный подход, так как так возможен
лишний учёт некоторых точек.
Тестовый пример:
[1 5]
[2 6]
[4 7]
Верный ответ здесь 1, но по вашему алгоритму, если я его верно, понял выдаст 3.
Так как нужно найти минимальное число точек, то нужно для начала заменить все отрезки
на их взаимные пересечения, если таковые есть. Если нет их, то оставить как есть. Тогда
ответом будет число таких отрезков.
Для данного примера сначала произойдёт замена [1 5] [2 6] на [2 5], затем [2 5] и
[4 7] на [4 5]. В конце остался один отрезок, поэтому правильный ответ - 1.

По-другому задачу можно интерпретировать так: имеется бесконечная доска и на ней
расположены дощечки. Сколько минимум гвоздей нужно вбить для того, чтобы ни одну из
дощечек не вытащить?

Схематическое решение

Отсортировать массив по началу отрезка, в случае совпадения по концу O(n log n)
Сравнить отрезок со следующим: если конец первого больше или равен началу второго,
то заменить эти отрезки на один, с началом, совпадающим с началом второго отрезка,
с концом, равным min(конец первого, конец второго). В противном случае ничего не менять.
Повторять для полученного ту же самую операцию со следующим и так, пока не будет достигнут
конец массива. Число оставшихся элементов массива и будет искомым числом точек. O(n)

UPD

Для нахождения искомого множества точек нужно взять по одной точке из каждого оставшегося
отрезка.


Ответ 3

Ну вот такой вариант:


Положим что два отрезка эквивалентны, если они пересекаются хотя бы в одной точке
Создадим класс отрезок и напишем соответствующий компаратор, в случае если он возвращает
0 будем пересекать наш текущий отрезок с тем которому он эквивалентен
Поочерёдно сложим всё это счастье в Set(т.е. у нас там будут лежать пересечения эквивалентных
в нашем смысле отрезков)
Пробежимся по Set'у и из каждого лежащего там отрезка возьмём по любой одной точке


Вроде должно работать(надеюсь у вас есть тесты)


Ответ 4

Если я правильно понял, речь идёт о пересечении отрезков.
Пересечением нескольких одномерных отрезков является отрезок, левый конец которого
является максимумом левых концов отрезков, а правый - минимумом правых концов.
Если полученный левый конец находится справа от полученного правого конца, результат
- пустое множество.
P.S. Поскольку "множество точек минимального размера" есть пустое множество, условие
требуется подправить.