java - 在 Joda-Time 间隔中查找漏洞

Question

我有Joda-Time 间隔列表

List<Interval> intervals = new ArrayList<Interval>();

和另一个 Joda-Time 间隔（搜索时间间隔），如下图所示。

我需要编写 Java 函数来及时找到漏洞并List<Interval>以红色间隔返回。

Answer 1

建立在 fge 的响应之上 - 以下版本实际上处理了这两种情况（当大间隔大于正在搜索的间隔的极值时 + 大间隔实际上更小......或一侧更小的情况）

你可以在https://github.com/erfangc/JodaTimeGapFinder.git看到完整的代码和测试

public class DateTimeGapFinder {

    /**
     * Finds gaps on the time line between a list of existing {@link Interval}
     * and a search {@link Interval}
     * 
     * @param existingIntervals
     * @param searchInterval
     * @return The list of gaps
     */
    public List<Interval> findGaps(List<Interval> existingIntervals, Interval searchInterval) {
        List<Interval> gaps = new ArrayList<Interval>();

        DateTime searchStart = searchInterval.getStart();
        DateTime searchEnd = searchInterval.getEnd();

        if (hasNoOverlap(existingIntervals, searchInterval, searchStart, searchEnd)) {
            gaps.add(searchInterval);
            return gaps;
        }

        // create a sub-list that excludes interval which does not overlap with
        // searchInterval
        List<Interval> subExistingList = removeNoneOverlappingIntervals(existingIntervals, searchInterval);
        DateTime subEarliestStart = subExistingList.get(0).getStart();
        DateTime subLatestStop = subExistingList.get(subExistingList.size() - 1).getEnd();

        // in case the searchInterval is wider than the union of the existing
        // include searchInterval.start => earliestExisting.start
        if (searchStart.isBefore(subEarliestStart)) {
            gaps.add(new Interval(searchStart, subEarliestStart));
        }

        // get all the gaps in the existing list
        gaps.addAll(getExistingIntervalGaps(subExistingList));

        // include latestExisting.stop => searchInterval.stop
        if (searchEnd.isAfter(subLatestStop)) {
            gaps.add(new Interval(subLatestStop, searchEnd));
        }
        return gaps;
    }

    private List<Interval> getExistingIntervalGaps(List<Interval> existingList) {
        List<Interval> gaps = new ArrayList<Interval>();
        Interval current = existingList.get(0);
        for (int i = 1; i < existingList.size(); i++) {
            Interval next = existingList.get(i);
            Interval gap = current.gap(next);
            if (gap != null)
                gaps.add(gap);
            current = next;
        }
        return gaps;
    }

    private List<Interval> removeNoneOverlappingIntervals(List<Interval> existingIntervals, Interval searchInterval) {
        List<Interval> subExistingList = new ArrayList<Interval>();
        for (Interval interval : existingIntervals) {
            if (interval.overlaps(searchInterval)) {
                subExistingList.add(interval);
            }
        }
        return subExistingList;
    }

    private boolean hasNoOverlap(List<Interval> existingIntervals, Interval searchInterval, DateTime searchStart, DateTime searchEnd) {
        DateTime earliestStart = existingIntervals.get(0).getStart();
        DateTime latestStop = existingIntervals.get(existingIntervals.size() - 1).getEnd();
        // return the entire search interval if it does not overlap with
        // existing at all
        if (searchEnd.isBefore(earliestStart) || searchStart.isAfter(latestStop)) {
            return true;
        }
        return false;
    }
}

Answer 2

快速浏览一下 Interval API 给出了这个（未测试）：

// SUPPOSED: the big interval is "bigInterval"; the list is "intervals"

// Intervals returned
List<Interval> ret = new ArrayList<>();


Interval gap, current, next;

// First, compute the gaps between the elements in the list

current = intervals.get(0);
for (int i = 1; i < intervals.size(); i++) {
    next = intervals.get(i);
    gap = current.gap(next);
    if (gap != null)
        ret.add(gap);
    current = next;
}

// Now, compute the time difference between the starting time of the first interval
// and the starting time of the "big" interval; add it at the beginning

ReadableInstant start, end;

start = bigInterval.getStart();
end = intervals.get(0).getStart();

if (start.isBefore(end))
    ret.add(0, new Interval(start, end));

//
// finally, append the time difference between the ending time of the last interval
// and the ending time of the "big" interval

// next still contains the last interval
start = next.getEnd();
end = bigInterval.getEnd();
if (start.isBefore(end))
    ret.add(new Interval(start, end));

return ret;

Answer 3

fge的答案似乎是正确的，尽管我没有运行未经测试的代码。

术语“间隙”似乎是您所谓的“孔”的更常见术语。

请参阅Katja Christiansen 的这个答案，它充分利用gap了 Interval 类的方法。

Interval gapInterval = interval_X.gap( interval_Y );
// … Test for null to see whether or a gap exists.

如果它们之间的持续时间不为零，则会返回一个新的 Interval 对象。如果间隔重叠或邻接，则返回 null。请注意，Interval 类还提供方法overlap，abuts如果您对这些特定条件感兴趣。

当然，您的 Interval 对象集合必须进行排序才能正常工作。