题解

题面描述

某景点可在任意时刻接待游客，游客到访的时间不定，时长不定。给定若干游客的到访时刻和离开时刻数据，求景点接待游客的总时长。注意，景点在同一时刻可以接待多名游客，但总时长只计算景点被接待的时间段长度，不重复计算重叠的时间。

思路

本题的核心在于计算多个时间区间的并集长度。具体步骤如下：

1. 读取所有游客的时间区间：每个游客有一个起始时间和结束时间。

2. 排序时间区间：将所有区间按起始时间进行排序，确保后续处理时能够顺序遍历。

3. 合并重叠区间：

   • 初始化一个变量记录当前合并区间的起始和结束时间。
   • 遍历排序后的所有区间：
     • 如果当前区间的起始时间小于或等于当前合并区间的结束时间，则说明两个区间重叠，将当前合并区间的结束时间更新为两者的较大值。
     • 否则，当前合并区间结束，将其长度加入总时长，并将当前区间作为新的合并区间。

4. 计算总时长：将所有合并后的区间长度相加，得到总时长。

cpp

#include <bits/stdc++.h>
using namespace std;

// 定义一个结构体来存储每个游客的时间区间
struct Interval {
    int start;
    int end;
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int m;
    cin >> m;
    
    // 存储所有游客的时间区间
    vector<Interval> intervals(m);
    for(int i=0; i<m; ++i){
        cin >> intervals[i].start >> intervals[i].end;
    }
    
    if(m == 0){
        cout << "0";
        return 0;
    }
    
    // 按起始时间排序
    sort(intervals.begin(), intervals.end(), [&](const Interval &a, const Interval &b) -> bool{
        if(a.start != b.start)
            return a.start < b.start;
        return a.end < b.end;
    });
    
    // 初始化合并区间
    int current_start = intervals[0].start;
    int current_end = intervals[0].end;
    long long total_duration = 0;
    
    for(int i=1; i<m; ++i){
        if(intervals[i].start <= current_end){
            // 有重叠，更新当前合并区间的结束时间
            current_end = max(current_end, intervals[i].end);
        }
        else{
            // 无重叠，累加当前合并区间的长度
            total_duration += (long long)(current_end - current_start);
            // 更新当前合并区间为新的区间
            current_start = intervals[i].start;
            current_end = intervals[i].end;
        }
    }
    
    // 累加最后一个合并区间的长度
    total_duration += (long long)(current_end - current_start);
    
    cout << total_duration;
    return 0;
}

python

import sys

def main():
    import sys
    import sys
    sys.setrecursionlimit(1 << 25)
    m = int(sys.stdin.readline())
    intervals = []
    for _ in range(m):
        start, end = map(int, sys.stdin.readline().split())
        intervals.append((start, end))
    
    if m == 0:
        print(0)
        return
    
    # 按起始时间排序
    intervals.sort()
    
    current_start, current_end = intervals[0]
    total_duration = 0
    
    for i in range(1, m):
        start, end = intervals[i]
        if start <= current_end:
            # 有重叠，更新结束时间
            current_end = max(current_end, end)
        else:
            # 无重叠，累加当前区间长度
            total_duration += (current_end - current_start)
            current_start, current_end = start, end
    
    # 累加最后一个区间
    total_duration += (current_end - current_start)
    
    print(total_duration)

if __name__ == "__main__":
    main()

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    // 定义一个类来存储区间
    static class Interval implements Comparable<Interval>{
        int start;
        int end;
        
        Interval(int s, int e){
            this.start = s;
            this.end = e;
        }
        
        @Override
        public int compareTo(Interval other){
            if(this.start != other.start){
                return this.start - other.start;
            }
            return this.end - other.end;
        }
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        // 读取游客数量
        line = br.readLine();
        int m = Integer.parseInt(line);
        
        if(m == 0){
            System.out.println(0);
            return;
        }
        
        Interval[] intervals = new Interval[m];
        for(int i=0; i<m; i++){
            line = br.readLine();
            String[] parts = line.trim().split("\\s+");
            int start = Integer.parseInt(parts[0]);
            int end = Integer.parseInt(parts[1]);
            intervals[i] = new Interval(start, end);
        }
        
        // 按起始时间排序
        Arrays.sort(intervals);
        
        int current_start = intervals[0].start;
        int current_end = intervals[0].end;
        long total_duration = 0;
        
        for(int i=1; i<m; i++){
            Interval interval = intervals[i];
            if(interval.start <= current_end){
                // 有重叠，更新结束时间
                current_end = Math.max(current_end, interval.end);
            }
            else{
                // 无重叠，累加当前区间长度
                total_duration += (current_end - current_start);
                // 更新当前区间
                current_start = interval.start;
                current_end = interval.end;
            }
        }
        
        // 累加最后一个区间
        total_duration += (current_end - current_start);
        
        System.out.println(total_duration);
    }
}

题目内容

某景点可在任意时刻接待游客，游客到访的时间不定，时长不定，现给定若干游客到访时刻和离开时刻的数据，求景点接待游客的总时长。

输入描述

输入为多行

第$1$行，整数$m$($0<m<10^6$)，表示有$m$个游客;

第$2$行至第$m+1$行，每行为$2$个正整数$start\ end$，以空格隔开，分别表示每位游客游玩的起止时刻($0<start<10^5,0<end<10^5$, $0<end-start<10^3$)

输入保证正确性，无需额做输入校验

输出描述

输出为整数$k$，表示景点接待游客的总时长(景点在同一时刻可接待多名游客)

样例1

输入

3
10 11
1 2 
1 5

输出

5

说明

景点接待游客的时间分为两段:$[1,5],[10,11]$,长度和为$5$

样例2

输入

1
1 12

输出

11

说明

景点接待游客的时间为$1$段:$[1,12]$长度和为$11$