问题描述

小H和小W来到了一条街上，两人分开买菜，他们买菜的过程可以描述为，去店里买一些菜然后去旁边的一个广场把菜装上车，两人都要买n种菜，所以也都要装n次车。具体的，对于小H来说有n个不相交的时间段[a₁,b₁],[a₂,b₂]...[a_n,b_n]在装车，对于小W来说有n个不相交的时间段[c₁,d₁],[c₂,d₂]...[c_n,d_n]在装车。其中，一个时间段[s, t]表示的是从时刻s到时刻t这段时间，时长为t-s。
　　由于他们是好朋友，他们都在广场上装车的时候会聊天，他们想知道他们可以聊多长时间。

输入格式

输入的第一行包含一个正整数n，表示时间段的数量。
　　接下来n行每行两个数a_i，b_i，描述小H的各个装车的时间段。
　　接下来n行每行两个数c_i，d_i，描述小W的各个装车的时间段。

输出格式

输出一行，一个正整数，表示两人可以聊多长时间。

样例输入

样例输出

数据规模和约定

对于所有的评测用例，1 ≤ n ≤ 2000, a_i< b_i< a_i+1，c_i< d_i< c_i+1,对于所有的i(1 ≤ i ≤ n)有，1 ≤ a_i, b_i, c_i, d_i ≤ 1000000。

编程语言：Python

解题思想：

最开始用的是判断时间段的方法，但是会有多种情况需要判断，突然想起Python中集合之间有交集运算。所以有些题目如果掌握了API会轻松很多。

1.因为题目给定了同一个人的时间段都是不相交的，可以使用Python中的集合进行存储

2.将每个人所有的时间点都存放到集合中，可以非常巧妙利用Python中两个集合的交集来获得小H和小W聊天的时长

3.HEnd和WEnd的循环边界不用加1，例如H:(1,3),W:(2,4)，则相交的时间点有2,3，但题目要求的是聊天的时长，因此时长只有3-2=1

时间复杂度：O(n^2)

IDE代码如下：

NOT = int(input())  # 输入时间段的数量
H, W = set(), set()
 
for i in range(NOT):
    HStart, HEnd = map(int, input().split())  # 输入小H每次装车的开始时刻与结束时刻
    for j in range(HStart, HEnd):
        H.add(j)  # 将时间段内的每个点存入小H的时间点集合
for i in range(NOT):
    WStart, WEnd = map(int, input().split())  # 输入小W每次装车的开始时刻与结束时刻
    for j in range(WStart, WEnd):
        W.add(j)  # 将时间段内的每个点存入小W的时间点集合
print((H.intersection(W).__len__()))  # 取小H时间点集合与小W时间点集合的交集，这个交集就是他们能够聊天的时间

< >

评论板

共有 5 条评论

Gealpaste

cialis prescription online In the cases of axillary lymph node dissection ALND, only 1

2023-05-11 09:54 回复
jordans for cheap

Read reviews and was a little hesitant since I had already inputted my order. or even but thank god, I had no issues. much received item in a timely matter, they are in new condition. regardless so happy I made the purchase. Will be definitely be purchasing again.
jordans for cheap https://www.realjordansshoes.com/

2023-05-16 05:39 回复
authentic cheap jordans

Read reviews and was a little hesitant since I had already inputted my order. and it could be but thank god, I had no issues. similar to received item in a timely matter, they are in new condition. you ultimately choose so happy I made the purchase. Will be definitely be purchasing again.
authentic cheap jordans https://www.retrocheapjordansshoes.com/

2023-05-16 14:41 回复
cheap jordans for sale

Read reviews and was a little hesitant since I had already inputted my order. or possibly a but thank god, I had no issues. the same as received item in a timely matter, they are in new condition. no matter what so happy I made the purchase. Will be definitely be purchasing again.
cheap jordans for sale https://www.realjordansretro.com/

2023-05-17 01:48 回复
intuido

Various other skin lesions have been described, including erythema multiforme and erythema nodosum buy cialis online in usa She knew my cycles better than I did

2023-06-14 20:18 回复

CCF-CSP_20180902:买菜