java - 迭代时间复杂度为O（log（N））的TreeSet(Iterate a TreeSet with a Time Complexity of O(log(N)))

Question

I currently have a TreeSet of WorkShift s.

(我目前有一个WorkShift的TreeSet。)

A WorkShift instance contains following information and methods:

(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 consists of WorkShift .

(一个WorkDay由WorkShift 。)

It's a TreeSet named shifts of WorkShifts , which is sorted after their start time.

(这是一个名为shifts of WorkShifts的TreeSet，它在start时间之后排序。)

Its class file looks like this:

(它的类文件如下所示：)

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));

}

Now I'd like to add a method getFirstShiftByDuration that gets an int duration as parameter and returns the first shift of the shifts set that has this duration, all this while keeping a max time complexity of O(log(N)) .

(现在，我想添加一个方法getFirstShiftByDuration ，该方法获取一个int duration作为参数并返回具有该持续时间的shifts集的第一个班次，同时保持最大时间复杂度O（log（N）） 。)

The 'empty' getFirstShiftByDuration looks like this:

(“空” getFirstShiftByDuration如下所示：)

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

        /*TODO*/
    }

Normally, I would have created a for-loop, iterated the set and looked for that specific duration.

(通常，我会创建一个for循环，遍历该集合并查找该特定持续时间。)

But now that there is the runtime restriction of O(log(N)), I am heavily limited in my options and pre-implemented methods I could make use of.

(但是，由于现在存在O（log（N））的运行时限制，因此我在选择和可以使用的预实现方法上受到很大限制。)

The set itself furthermore consists of elements defined by just their start and end .

(该集合本身还由仅由其start和end定义的元素组成。)

I can't figure out how I could use pre-defined TreeSet methods and compare them by their durations when it's not even an attribute.

(我无法弄清楚如何使用预定义的TreeSet方法，甚至在它不是属性时也可以通过它们的持续时间进行比较。)

Is there any way to solve this without creating new classes and exceeding the O(log(N)) runtime restriction?

(有什么方法可以解决此问题，而无需创建新类并超出O（log（N））运行时限制？)

  ask by Two-Tu translate from so

Answer 1

等待大神答复