Java中拆分重叠DateRange为独立时段并保留非重叠区间的问题

需求说明 #

在Java场景下，我们需要处理包含自定义DateRange对象的列表，将所有重叠的日期区间拆分为按重叠程度划分的独立时段，非重叠的区间则保持原样。

输入示例 #

List<DateRange> inputList = new ArrayList<>();
inputList.add(new DateRange(LocalDate.of(2023, 7, 1), LocalDate.of(2023, 7, 10)));
inputList.add(new DateRange(LocalDate.of(2023, 7, 5), LocalDate.of(2023, 7, 30)));
inputList.add(new DateRange(LocalDate.of(2023, 7, 10), LocalDate.of(2023, 7, 20)));
inputList.add(new DateRange(LocalDate.of(2023, 7, 15), LocalDate.of(2023, 7, 20)));
inputList.add(new DateRange(LocalDate.of(2023, 8, 1), LocalDate.of(2023, 8, 20)));

预期输出 #

拆分后应得到以下独立时段：

List<DateRange> resultList = new ArrayList<>();
resultList.add(new DateRange(LocalDate.of(2023, 7, 1), LocalDate.of(2023, 7, 4)));
resultList.add(new DateRange(LocalDate.of(2023, 7, 5), LocalDate.of(2023, 7, 9)));
resultList.add(new DateRange(LocalDate.of(2023, 7, 10), LocalDate.of(2023, 7, 10)));
resultList.add(new DateRange(LocalDate.of(2023, 7, 11), LocalDate.of(2023, 7, 14)));
resultList.add(new DateRange(LocalDate.of(2023, 7, 15), LocalDate.of(2023, 7, 20)));
resultList.add(new DateRange(LocalDate.of(2023, 7, 21), LocalDate.of(2023, 7, 30)));
resultList.add(new DateRange(LocalDate.of(2023, 8, 1), LocalDate.of(2023, 8, 20)));

当前错误输出 #

现有代码运行后得到的结果不符合预期：

1. 2023-07-01 - 2023-07-04
2. 2023-07-05 - 2023-07-09
3. 2023-07-10 - 2023-07-20
4. 2023-07-15 - 2023-07-20
5. 2023-07-21 - 2023-07-30
6. 2023-08-01 - 2023-08-20

现有代码 #

import java.time.LocalDate;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class DateRange {
    LocalDate start;
    LocalDate end;

    public DateRange(LocalDate start, LocalDate end) {
        this.start = start;
        this.end = end;
    }

    @Override
    public String toString() {
        return "DateRange [start=" + start + ", end=" + end + "]";
    }
}

public class Main1 {
    public static void main(String[] args) {
        List<DateRange> inputList = new ArrayList<>();
        inputList.add(new DateRange(LocalDate.of(2023, 7, 1), LocalDate.of(2023, 7, 10)));
        inputList.add(new DateRange(LocalDate.of(2023, 7, 5), LocalDate.of(2023, 7, 30)));
        inputList.add(new DateRange(LocalDate.of(2023, 7, 10), LocalDate.of(2023, 7, 20)));
        inputList.add(new DateRange(LocalDate.of(2023, 7, 15), LocalDate.of(2023, 7, 20)));
        inputList.add(new DateRange(LocalDate.of(2023, 8, 1), LocalDate.of(2023, 8, 20)));

        List<DateRange> resultList = processDateRanges(inputList);
        resultList.forEach(System.out::println);
    }

    public static List<DateRange> processDateRanges(List<DateRange> inputList) {
        List<DateRange> result = new ArrayList<>();
        Collections.sort(inputList, Comparator.comparing(r -> r.start));

        for (int i = 0; i < inputList.size(); i++) {
            DateRange current = inputList.get(i);
            LocalDate start = current.start;
            LocalDate end = current.end;

            for (int j = i + 1; j < inputList.size(); j++) {
                DateRange next = inputList.get(j);
                if (next.start.isAfter(end.plusDays(1))) break;

                if (next.start.isAfter(start)) {
                    result.add(new DateRange(start, next.start.minusDays(1)));
                }
                if (next.end.isBefore(end)) {
                    result.add(new DateRange(next.start, next.end));
                    start = next.end.plusDays(1);
                } else {
                    start = next.start;
                    end = next.end;
                }
            }
            result.add(new DateRange(start, end));
            while (i + 1 < inputList.size() && inputList.get(i + 1).start.isBefore(end.plusDays(1))) {
                i++;
            }
        }

        return result;
    }
}

问题分析 #

现有代码通过两两比较区间来拆分，但这种方式无法处理多个区间重叠时的所有关键边界点（比如示例中的2023-07-10、2023-07-15），导致拆分后的区间仍包含重叠部分，没有按重叠程度彻底拆分。

修正方案 #

正确思路是先收集所有原区间的起止日期作为关键节点，排序去重后，遍历相邻节点生成小区间，同时验证每个小区间是否被至少一个原区间覆盖，确保生成的区间都是有效的独立时段：

修正后的代码 #

import java.time.LocalDate;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class DateRange {
    LocalDate start;
    LocalDate end;

    public DateRange(LocalDate start, LocalDate end) {
        this.start = start;
        this.end = end;
    }

    @Override
    public String toString() {
        return "DateRange [start=" + start + ", end=" + end + "]";
    }

    // 判断当前区间是否包含目标小区间
    public boolean contains(LocalDate targetStart, LocalDate targetEnd) {
        return !targetStart.isAfter(this.end) && !targetEnd.isBefore(this.start);
    }
}

public class Main1 {
    public static void main(String[] args) {
        List<DateRange> inputList = new ArrayList<>();
        inputList.add(new DateRange(LocalDate.of(2023, 7, 1), LocalDate.of(2023, 7, 10)));
        inputList.add(new DateRange(LocalDate.of(2023, 7, 5), LocalDate.of(2023, 7, 30)));
        inputList.add(new DateRange(LocalDate.of(2023, 7, 10), LocalDate.of(2023, 7, 20)));
        inputList.add(new DateRange(LocalDate.of(2023, 7, 15), LocalDate.of(2023, 7, 20)));
        inputList.add(new DateRange(LocalDate.of(2023, 8, 1), LocalDate.of(2023, 8, 20)));

        List<DateRange> resultList = processDateRanges(inputList);
        resultList.forEach(System.out::println);
    }

    public static List<DateRange> processDateRanges(List<DateRange> inputList) {
        List<DateRange> result = new ArrayList<>();
        if (inputList.isEmpty()) {
            return result;
        }

        // 收集所有关键日期节点：所有start和end
        Set<LocalDate> dateNodes = new HashSet<>();
        for (DateRange range : inputList) {
            dateNodes.add(range.start);
            dateNodes.add(range.end);
        }

        // 将节点排序
        List<LocalDate> sortedNodes = new ArrayList<>(dateNodes);
        Collections.sort(sortedNodes);

        // 遍历相邻节点，生成小区间并验证有效性
        for (int i = 0; i < sortedNodes.size() - 1; i++) {
            LocalDate currentStart = sortedNodes.get(i);
            LocalDate nextStart = sortedNodes.get(i + 1);
            LocalDate currentEnd = nextStart.minusDays(1);

            // 跳过无效区间（比如start > end）
            if (currentStart.isAfter(currentEnd)) {
                continue;
            }

            // 检查该小区间是否被至少一个原区间覆盖
            boolean isCovered = false;
            for (DateRange range : inputList) {
                if (range.contains(currentStart, currentEnd)) {
                    isCovered = true;
                    break;
                }
            }

            if (isCovered) {
                result.add(new DateRange(currentStart, currentEnd));
            }
        }

        return result;
    }
}

代码解析 #

1. 收集关键节点：提取所有原区间的start和end日期，存入集合去重，确保每个边界点只保留一次。
2. 排序节点：将关键日期按升序排列，相邻节点之间的区间即为最小拆分单元。
3. 生成并验证小区间：遍历每一对相邻节点，生成[currentStart, currentEnd]的小区间，同时检查该区间是否被至少一个原区间覆盖，避免生成无意义的空区间或未被覆盖的区间。
4. 边界处理：通过nextStart.minusDays(1)确保区间是闭区间，符合原DateRange的定义。

运行修正后的代码，即可得到与预期一致的拆分结果。

内容的提问来源于stack exchange，提问作者venu