#YHW206. 育华学校的活动时间安排问题

育华学校的活动时间安排问题

题目:育华学校的活动时间安排问题

题目描述

育华学校正在筹备一系列的活动,这些活动将在不同的时间区间内进行。已知有 NN 个活动,每个活动的时间区间为 [ai,bi][a_i,b_i],表示该活动从时刻 aia_i 开始,到时刻 bib_i 结束。现在需要你求出这些活动在时间轴上所覆盖的总时长。

例如,若有三个活动,其时间区间分别为 [1,10][1,10][12,20][12,20][15,30][15,30],那么这些活动在时间轴上覆盖的总时长为 2929(因为 [1,10][1,10] 覆盖时长为 101+1=1010 - 1 + 1 = 10[12,20][12,20][15,30][15,30] 可以合并为 [12,30][12,30]3012+1=1930 - 12 + 1 = 19,总计 2929)。

输入格式

第一行一个正整数 NN,表示活动的数量。

接下来 NN 行,每行两个正整数,表示 aia_ibib_i,分别代表第 ii 个活动的开始时间和结束时间。

输出格式

共一行,一个正整数,为所有活动覆盖后的总时长。

样例 #1

样例输入 #1

3
1 10
12 20
15 30

样例输出 #1

29

样例 #2

样例输入 #2

5
5 10
2 8
1 12
15 20
18 25

样例输出 #2

23

数据范围

  • 对于 40%40\% 的数据,N1000N \leq 10001ai<bi100001 \leq a_i < b_i \leq 10000
  • 对于 100%100\% 的数据,N105N \leq 10^51ai<bi10171 \leq a_i < b_i \leq 10^{17}