Задача о покрытии отрезков точками на Java

Решим задачу о покрытии отрезков точками.

Дано N отрезков на прямой. Требуется покрыть их наименьшим числом точек. Нужно найти наименьшее множество точек такое, что каждому отрезку принадлежит хотя бы одна точка.

На обучающих ресурсах эта задача имеет следующую формулировку:

Given n intervals. Find the set of points having the minimum size (cardinality), for which each of the given intervals contains at least one of the points.
The first line given 1\leq n \leq 100 – number of intervals. Each of the next n lines contains two 0\leq l \leq r \leq 10^9 numbers, setting the beginning and the end of the interval. Output the minimum size of the set m and the m points themselves. If there are several such sets, output any of them.

Пример решения задачи

Для примера возьмем 6 отрезков, в качестве входных данных. В таблице указаны левые и правые границы:

№ отрезка 1 2 3 4 5 6
Края L:4; R:7 L:1; R:3 L:2; R:5 L:5; R:6 L:6; R:8 L:3; R:4

Да графике данные отрезки имеют следующий вид (на самом деле все они строятся на одной прямой, но лучше их начертить раздельно, чтобы видеть, с чем мы работаем):

Отрезки

Алгоритм покрытия отрезков точками

Берем все концы отрезков (как левые, так и правые) и сортируем их. Для каждой точки сохраним номер отрезка. Также каким концом его она является (левым или правым). Учтем, что если есть несколько точек с одной координатой, то сначала будут идти левые концы, потом правые.

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

По окончании работы алгоритма все отрезки будут покрыты наименьшим числом точек.

Таким образом, результатом обработки входных данных из таблицы выше являются две точки — 3 и 6:

Решенная задача

Показать текст ->

Заметим, что соединив эти точки в отрезок, мы «захватим» им все отрезки, которые у нас есть.

В результате точка может быть одна, захватывающая все отрезки.

Пример входных отрезков, которые захватывает одна точка

Предположим, у нас есть следующие входные данные:

№ отрезка 1 2 3
Края L:1; R:3 L:2; R:5 L:3; R:6

На графике решение будет иметь такой вид:

Все отрезки покрыты одной точкой

Нетрудно догадаться, что ответом является точка 3.

Реализация алгоритма покрытия отрезков на Java

Код Java в моем исполнении имеет следующий вид:

import java.util.*;

class Spot implements Comparable{
    int numOtrezok, spotval;
    char side;

    public Spot(int numOtrezok, int spotval, char side) {
        this.numOtrezok = numOtrezok;
        this.spotval = spotval;
        this.side = side;
    }

    @Override
    public int compareTo(Object o) {
        Spot spot = (Spot)o;
        int numres = this.spotval > spot.spotval ? 1 : this.spotval < spot.spotval ? -1 : 0;
        switch (numres){
            case 0: return side == 'R' ? 1 : -1;
            default: return numres;
        }
    }
}

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //Количество отрезков
        int n = sc.nextInt();
        int [][] otr = new int[n][];
        sc.nextLine();
        List<Spot> listSpots = new ArrayList<>();
        List<Integer> stack = new ArrayList<>();
        List<Integer> result = new ArrayList<>();

        //Получаем края отрезков и записываем в массив
        for (int i = 0; i < n; i++) {
            String[] split = sc.nextLine().split(" ");
            otr[i] = new int[2];
            otr[i][0] = Integer.parseInt(split[0]);
            otr[i][1] = Integer.parseInt(split[1]);
        }

        //Заполняем массив точек
        for (int i = 0; i < n; i+=1) {
            listSpots.add(new Spot(i + 1, otr[i][0], 'L'));
            listSpots.add(new Spot(i + 1, otr[i][1], 'R'));
        }

        //Сортируем массив точек
        listSpots.sort(Comparator.naturalOrder());

        //Следуем алгоритму, описанному в статье
        for (int i = 0; i < listSpots.size(); i++) {
            if(listSpots.get(i).side == 'L')
                stack.add(listSpots.get(i).numOtrezok);
            else if(stack.contains(listSpots.get(i).numOtrezok)){
                result.add(listSpots.get(i).spotval);
                stack.clear();
            }
        }

        System.out.println(result.size());
        result.forEach(integer -> System.out.print(integer + " "));
    }   
}

На вход подается количество отрезков и их края. Создан специальный класс Spot, имплементирующий интерфейс Comparable для правильной сортировки. Сложности только в заполнении коллекций. Остальное все по алгоритму.

В результате работы программы будет выведено количество точек и сами точки.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *