Итерация TreeSet с временной сложностью O (log (N)) - PullRequest
Новая
       74

Итерация TreeSet с временной сложностью O (log (N))

0 голосов
/ 01 декабря 2019

У меня есть TreeSet WorkShift с. Экземпляр WorkShift содержит следующую информацию и методы: 

package work;


public class WorkShift {

    private final int start;

    private final int end;

    private final int duration;

    /**
     * Constructor.
     * 
     * @param start 
     * @param end 
     */
    public TTInterval(int start, int end) {
        this.start = start;
        this.end = end;
        this.duration = end - start + 1; //
    }

    /**
     * @return Start
     */
    public int getStart() {
        return start;
    }

    /**
     * @return End
     */
    public int getEnd() {
        return end;
    }

    /**
     * @return Duration
     */
    public int getDuration() {
        return duration;
    }
}

A WorkDay состоит из WorkShift. Это TreeSet с именем shifts из WorkShifts, который сортируется по истечении start времени. Его файл класса выглядит следующим образом: 

package work;

import java.util.Arrays;
import java.util.Comparator;
import java.util.TreeSet;

public class WorkDay {
    /**
     * Set of shifts sorted by their start time.
     */
    private final TreeSet<WorkShift> shifts =
            new TreeSet<>(Comparator.comparing(WorkShift::getStart));

}

Теперь я хотел бы добавить метод getFirstShiftByDuration, который получает int duration в качестве параметра и возвращает первый сдвиг набора shifts, который имеет этотдлительность, все это при сохранении максимальной временной сложности O (log (N)) .

«Пустой» getFirstShiftByDuration выглядит следующим образом: 

    /**
     * Returns the workShift with the duration we are looking for
     * 
     * @param duration
     * @pre duration &gt; 0
     * 
     * @return First workShift found with that duration.
     */
    public workShift getfirstWorkShiftByDuration(int duration) {
        assert duration > 0;

        /*TODO*/
    }

Обычно, я бы создал цикл for, повторил бы набор и искал эту конкретную продолжительность. Но теперь, когда есть ограничение времени выполнения O (log (N)), я сильно ограничен в своих опциях и предварительно реализованных методах, которые я мог бы использовать.

Сам набор, кроме того, состоит из элементов, определенныхтолько их start и end. Я не могу понять, как я мог бы использовать предопределенные методы TreeSet и сравнивать их по продолжительности, когда это даже не атрибут.

Есть ли способ решить эту проблему без создания новых классов и превышенияограничение времени выполнения O (log (N))?

...