首页 > 试题广场 >

聊天

[编程题]聊天
  • 热度指数：5415 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
A和B是好友，他们经常在空闲时间聊天，A的空闲时间为[a1 ,b1 ],[a2 ,b2 ]..[ap ,bp ]。B的空闲时间是[c1 +t,d1 +t]..[cq +t,dq +t],这里t为B的起床时间。这些时间包括了边界点。B的起床时间为[l,r]的一个时刻。若一个起床时间能使两人在任一时刻聊天，那么这个时间就是合适的，问有多少个合适的起床时间？

输入描述:
第一行数据四个整数：p,q,l,r（1≤p,q≤50,0≤l≤r≤1000)。接下来p行数据每一行有一对整数ai，bi(0≤aii+1>bi,ci+1>di


输出描述:
输出答案个数
示例1

输入

2 3 0 20
15 17
23 26
1 4
7 11
15 17

输出

20
算法知识视频讲解
开通博客
头像 觞乄默
发表于 2022-10-11 20:56:49
对于一个A的空闲时间段 [a, b] 和一个B的空闲时间段 [c, d]，我们要找的是：t取何值时，将 [c+t, d+t] 与 [a, b] 有非空交集？在草稿纸上简单画图模拟一下，可以得到 。当然，题目中还有一个限制：那就是B的起床时间要在 [l, r]之内。因此将 [d-a, b-c] 再与 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Just_tired
发表于 2023-03-03 19:41:11
#include <iostream> #include <bitset> using namespace std; int main() { bitset<2000> forA; bitset<2000> forB; int 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 贪吃的迪恩顶呱呱
发表于 2024-05-15 16:19:02
依次增加起床时间，将B的空闲时间不断后移，每次增加后判断是否与A的空闲时间相交 #include <iostream> #include <vector> using namespace std; // 判断两个时间段是否相交 bool isIntersect(pair&l 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 bandiaoz
发表于 2024-12-26 19:12:38
解题思路 这是一道区间重叠问题，主要思路如下： 问题分析： A有 个空闲时间区间 B有 个空闲时间区间 ， 从 到 需要找出有多少个 值使得A和B的时间区间有重叠 区间重叠意味着存在交集 解决方案： 枚举每个可能的 值 对每个 ，检查A的所有区间和B的所有区间是否存在重叠 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 动态规划 2016 蘑菇街 Java工程师
来自：美丽联合2016研发工...
难度：
70条回答 18795浏览

热门推荐

通过挑战的用户

查看代码

相关试题

聊天

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号