题解

题面描述

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

思路

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

题目内容

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

输入描述

输入为多行

第$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$

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写