贪心算法实现：基于开门关门时间数组计算门总开启时长

核心思路 #

问题本质是跟踪单门的开关状态，按时间顺序处理所有开门/关门操作，仅当状态变化时计算有效时长：

1. 事件整理：将所有开门、关门操作转化为带类型的事件，明确每个时间点的操作类型。
2. 事件排序：按时间升序排列事件；若时间相同，优先处理关门操作（避免同一时间先开门后关门导致错误计算）。
3. 状态跟踪：遍历事件，维护门的当前状态（开/关），仅当门从关闭转为开启时记录开始时间，从开启转为关闭时计算时长并累加。

伪代码 #

function calculateTotalOpenTime(A, B):
    events = []
    for i from 0 to len(A)-1:
        add (A[i], "open") to events
        add (B[i], "close") to events
    
    // 排序规则：时间升序，时间相同时关门事件优先
    sort events with comparator:
        if event1.time != event2.time:
            return event1.time - event2.time
        else:
            // "close" 优先级高于 "open"，让关门事件排在前面
            return -1 if event1.type == "close" else 1
    
    total_duration = 0
    is_open = False
    start_time = null
    
    for each event in events:
        time, type = event
        if type == "close":
            if is_open:
                total_duration += time - start_time
                is_open = False
                start_time = null
        else: // "open"
            if not is_open:
                is_open = True
                start_time = time
    
    return total_duration

Python 实现 #

def calculate_total_open_time(A, B):
    events = []
    for open_t, close_t in zip(A, B):
        events.append((open_t, 'open'))
        events.append((close_t, 'close'))
    
    # 排序：时间升序，时间相同则关门事件在前
    events.sort(key=lambda x: (x[0], 0 if x[1] == 'close' else 1))
    
    total = 0
    is_open = False
    start_time = None
    
    for time, event_type in events:
        if event_type == 'close':
            if is_open:
                total += time - start_time
                is_open = False
                start_time = None
        else:
            if not is_open:
                is_open = True
                start_time = time
    
    return total

# 测试示例
A = [3, 5, 7]
B = [4, 10, 12]
print(calculate_total_open_time(A, B))  # 输出 6

示例过程解析 #

1. 生成事件列表：[(3, 'open'), (4, 'close'), (5, 'open'), (7, 'open'), (10, 'close'), (12, 'close')]
2. 遍历事件：
   • 3点开门：门从关转开，记录开始时间3
   • 4点关门：门从开转关，累加时长4-3=1，总时长1
   • 5点开门：门从关转开，记录开始时间5
   • 7点开门：门已开，无操作
   • 10点关门：门从开转关，累加时长10-5=5，总时长6
   • 12点关门：门已关，无操作
3. 最终返回总时长6，与示例一致。

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