在Joda-Time间隔找到漏洞

Question

我有Joda-Time intervals的名单

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会给出这个（UNTESTED）：

// 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

answer by fge似乎是正确的，虽然我没有运行那些未经测试的代码。

对于你所谓的“漏洞”，“差距”一词似乎是一个更常见的术语。

请参阅this answer by Katja Christiansen，它充分利用了Interval类中的gap方法。

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

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

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