使用Python计算无重叠日期范围总天数的最优方案

这个需求在日程统计、资源占用计算这类场景里特别常见，最优解法的核心思路其实很直观——先把所有日期范围按起始时间排序，再合并重叠或相邻的区间，最后计算每个合并后区间的天数总和就行。下面我一步步拆解，再附上可运行的代码示例：

核心步骤详解 #

1. 给日期范围排序 #

这是整个流程的基础，只有把所有区间按起始日期从小到大排好序，我们才能用线性遍历的方式合并区间，不用反复回头检查之前的区间，效率最高。

2. 合并重叠/相邻区间 #

初始化一个空的合并列表，然后逐个遍历排序后的区间：

• 如果当前区间的起始时间 ≤ 合并列表最后一个区间的结束时间，说明两个区间重叠或者挨在一起，这时候就把最后一个区间的结束时间更新为两个区间结束时间的最大值（保留覆盖范围更广的）
• 如果当前区间和最后一个合并区间完全不重叠，就直接把它加入合并列表

3. 计算总天数 #

对每个合并后的区间，用结束日期减去起始日期，得到该区间的天数，然后把所有天数加起来就是最终结果。

Python代码示例 #

from datetime import datetime

def calculate_total_days(ranges):
    # 第一步：将字符串格式的日期转为datetime对象，并按起始日期排序
    formatted_ranges = []
    for r in ranges:
        # 注意这里的日期格式是月/日/年，根据实际格式可调整strptime的参数
        start = datetime.strptime(r['start'], '%m/%d/%Y')
        end = datetime.strptime(r['end'], '%m/%d/%Y')
        formatted_ranges.append({'start': start, 'end': end})
    
    sorted_ranges = sorted(formatted_ranges, key=lambda x: x['start'])
    
    # 处理空列表的边界情况
    if not sorted_ranges:
        return 0
    
    # 第二步：合并重叠或相邻的区间
    merged_intervals = [sorted_ranges[0]]
    for current in sorted_ranges[1:]:
        last_merged = merged_intervals[-1]
        if current['start'] <= last_merged['end']:
            # 重叠或相邻，更新结束日期为两者的最大值
            new_end = max(last_merged['end'], current['end'])
            merged_intervals[-1] = {'start': last_merged['start'], 'end': new_end}
        else:
            merged_intervals.append(current)
    
    # 第三步：计算总天数
    total_days = 0
    for interval in merged_intervals:
        # datetime对象相减得到timedelta，取days属性就是区间天数
        delta = interval['end'] - interval['start']
        total_days += delta.days
    
    return total_days

# 测试你给出的示例
ranges = [
    {'start': '1/1/2001', 'end': '1/1/2002'},
    {'start': '1/1/2000', 'end': '1/1/2002'},
    {'start': '1/1/2003', 'end': '1/1/2004'},
]

print(calculate_total_days(ranges))  # 输出：1096（731天+365天）

补充说明 #

• 这个方法的时间复杂度是O(n log n)，主要来自排序操作，这已经是这类区间合并问题的最优复杂度了——毕竟你不可能在比排序更快的时间内完成区间合并的逻辑。
• 日期格式可以根据实际情况调整strptime的参数，比如如果是年/月/日格式，就用'%Y/%m/%d'。
• 如果你的日期已经是datetime类型（不是字符串），可以跳过第一步的格式转换，直接排序就行。

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