各位大佬,这题啥思路呀,求助呀!
全部评论
构建一个数组arr,长为10^5+1,初始值都为0。遍历每一个乘客,根据该乘客的上车下车站点m和n,将arr的下标从m到n都加了,arr[m]到arr[n]之间都加1。遍历完所有乘客后,找到arr数组中最大的数字就是所需最多的座位数。
1 回复 分享
发布于 2020-04-21 18:06
请问这是哪里的题
点赞 回复 分享
发布于 2020-05-06 04:17
有原题链接吗
点赞 回复 分享
发布于 2020-04-21 17:57
对于乘客i,他和其他k个乘客的乘车区间有交集,那么k+1就是当前乘客乘车区间需要的最少座位数。对每个乘客,遍历其他乘客计算和它相交的乘客数,找所有乘客中最大的k,k+1就是了。复杂度n^2,不知道还能不能优化。
点赞 回复 分享
发布于 2020-04-21 00:00
考完了告诉你...
点赞 回复 分享
发布于 2020-04-19 13:51

相关推荐

点赞 评论 收藏
分享
xxxxOxo:该催就催,想要你的不会因为催就挂,催了就挂的是因为本来就要挂你
点赞 评论 收藏
分享
评论
3
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务