Поиск и обнаружение перекрытия в списке объектов по меткам времени начала и окончания

Question

У меня есть список, и я хочу обнаружить перекрывающиеся миссии в списке по атрибуту устройства String.Итак, Миссия будет выглядеть так:

public class Mission {
    private String id;
    private String device;
    private long startTime;
    private long endTime;
}

Я получаю Список и хочу вернуть тот же список с атрибутом подзадачи, установленным на «перекрытие», если:

• Есть еще одинмиссия одним и тем же устройством в течение его диапазона (временная отметка - временная отметка).

Напомним, что мне нужно пометить ВСЕ перекрытые миссии.Когда я найду их в списке, отметьте текущий (если совпадает) и обнаруженный в списке.

Я хочу сделать это с МЕНЬШЕЙ возможной стоимостью.Недорогие операции.

Answer 1

Если у вас есть возможность использовать дополнительную память, я могу предложить вам следующий алгоритм

1. Создать HashMap<String, TreeSet<Mission>> map, где device - это ключ.

2. TreeSet должен быть отсортирован по startTime.Пример new TreeSet<>(Comparator.comparingLong(Mission::getStartTime))

3. Инициализируйте map данными из вашего списка.Основная идея здесь - сгруппировать данные по device и упорядочить сгруппированные данные по startTime.

4. Затем выполнить итерацию по списку и применить следующий алгоритм:

   1. Найдите TreeSet на созданной карте: TreeSet<Mission> set = map.get(item.device).Если его размер равен 1, то вы можете перейти к следующему элементу в списке, поскольку этот единственный элемент набора имеет тот же идентификатор, что и исходный элемент из списка.
   2. Найти подмножество из набора, полученного на шаге 1, с элементами, что startTime ниже, чем item.endTime.Если его размер равен 1, то вы можете перейти к следующему элементу в списке, потому что этот единственный элемент подмножества имеет тот же идентификатор, что и исходный элемент из списка.Пример кода: set = set.headSet(new Mission().setStartTime(item.getEndTime()))
   3. Найти первый элемент в подмножестве из шага 2, что на endTime больше, чем в исходном item.startTime.Я бы порекомендовал вам переместить подмножество в обратном порядке set.descendingIterator() Если вы нашли его, и его идентификатор не равен идентификатору исходного элемента, то вы можете пометить элемент как перекрывающийся и перейти к следующему элементу вашего списка.В противном случае повторите шаг 3 для следующего элемента подмножества до конца.