AlgoMooc
你已开通华为OD训练营权益,还差最后一步——完成入营激活(兑换课程 + 加飞书 + 登记服务群),即可解锁全部课程与专属服务。去激活 →
← 返回题库

P3110. 观看文艺汇演

中等通过率 45% · 提交 1,872 · 通过 840
贪心排序区间DPDP/贪心

小慕负责筹备一场大型文艺汇演,园区内同时有多场演出在进行。由于每场演出都只能完整观看,不能中途入场或提前离场,而且小慕一次只能观看一场演出。此外,不同演出分布在园区的不同场地,因此连续两场观看之间至少需要留出 15 分钟的时间用于转场。 小慕是个狂热的文艺爱好者,希望能尽可能多地观看演出。 现在给定演出的时间安排表,请你帮小慕计算出他最多能观看多少场演出。

提示:带虚线的词点一下有通俗解释。

输入描述

<div data-page-id="WyahdwqCLoz0TNxY0Fmc8PUVnSg" data-docx-has-block-data="false"> <div style="white-space-collapse:preserve;" class="ace-line ace-line old-record-id-DzdkdAfLYonVIUxIYkAcWTUHnRh"> 第一行为一个数 <code>N</code>,表示演出场数,<code>1 <= N <= 1000</code>。 </div> <div style="white-space-collapse:preserve;" class="ace-line ace-line old-record-id-Vf62dc38jok8PtxOdsxc1zGFnIe"> 接下来 <code>N</code> 行,每行两个空格分割的整数,第一个整数 <code>T</code> 表示演出的开始时间,第二个整数 <code>L</code> 表示演出的持续时间,<code>T</code> 和 <code>L</code> 的单位为分钟,<code>0 <= T <= 1440, 0 < L <= 100</code>。 </div> </div> <span data-lark-record-data="{"isCut":false,"rootId":"WyahdwqCLoz0TNxY0Fmc8PUVnSg","parentId":"WyahdwqCLoz0TNxY0Fmc8PUVnSg","blockIds":[5,6],"recordIds":["DzdkdAfLYonVIUxIYkAcWTUHnRh","Vf62dc38jok8PtxOdsxc1zGFnIe"],"recordMap":{"DzdkdAfLYonVIUxIYkAcWTUHnRh":{"id":"DzdkdAfLYonVIUxIYkAcWTUHnRh","snapshot":{"type":"text","parent_id":"WyahdwqCLoz0TNxY0Fmc8PUVnSg","comments":[],"locked":false,"hidden":false,"author":"7115054903550050305","children":[],"text":{"initialAttributedTexts":{"text":{"0":"第一行为一个数 N,表示演出场数,1 <= N <= 1000。"},"attribs":{"0":"*0+8*0*1+1*0+8*0*1+e*0+1"}},"apool":{"numToAttrib":{"0":["author","7115054903550050305"],"1":["inlineCode","true"]},"nextNum":2}},"align":"","folded":false}},"Vf62dc38jok8PtxOdsxc1zGFnIe":{"id":"Vf62dc38jok8PtxOdsxc1zGFnIe","snapshot":{"type":"text","parent_id":"WyahdwqCLoz0TNxY0Fmc8PUVnSg","comments":[],"locked":false,"hidden":false,"author":"7115054903550050305","children":[],"text":{"initialAttributedTexts":{"text":{"0":"接下来 N 行,每行两个空格分割的整数,第一个整数 T 表示演出的开始时间,第二个整数 L 表示演出的结束时间,T 和 L 的单位为分钟,0 <= T <= 1440, 0 < L <= 100。"},"attribs":{"0":"*0+4*0*1+1*0+l*0*1+1*0+h*0*1+1*0+b*0*1+1*0+3*0*1+1*0+8*0*1+s*0+1"}},"apool":{"numToAttrib":{"0":["author","7115054903550050305"],"1":["inlineCode","true"]},"nextNum":2}},"align":"","folded":false}},"WyahdwqCLoz0TNxY0Fmc8PUVnSg":{"id":"WyahdwqCLoz0TNxY0Fmc8PUVnSg","snapshot":{"type":"page","parent_id":"","comments":[],"locked":false,"hidden":false,"author":"7115054903550050305","children":["doxcnwSnjjvJWvNQ84L4FO21tld","VYObd3eJ2oh6aZxQpEkcapiwnEg","FU9Udeb5to73FDxcGdhcU3ACnNh","DzdkdAfLYonVIUxIYkAcWTUHnRh","Vf62dc38jok8PtxOdsxc1zGFnIe","TVN8dLDBioC0JXxWe1CcsJdXnVH","ZvjKdHzj7o2yiPxK6otcRwtbn0b","CyCQd59zYokQgyxfXZjcm7stn7f","YKPEdfqsko4uf1xTaQLcAF2Cnfg","HOk0ddvp5o4iMExIuJncbqP4nsO","KUMZdLVGlo0npex4wHAcod7Hnoe","Iz0XdG4AAoaUvnxJwyecf1xanhb","Gw9ldUs7LoGNMMx6WaAcAA1Mn9b","BYgedP5KIoD7lyxMDtGcQ66DngY","X1r1dvrRPosSs5xWBj3c4rcdncg","VODxdvqryoq1Ezxipp8cV3Ltnyh","BMsvdkq0ioJbSGxHZZkcFL6znId","XVNHdERrKo5IjAxgFzbcEMfgn1g","LKYMdmLAFoMBEYxCaovcO0UQnAf","Mgsod6OO0oLKiNxM5TdcvsQfnKf","HeKSdw5YUowa0Dxjhr5cEIEZnOc","IvhLdfPa8o3n1TxVsDyc58FZnge","DL5DdWuOtou7PcxoNg6cmKrlnog","DL9udV6VSoysvaxtJSccCnxdn9Q","KaBzdLkSjozHSsx1nftcdGnOnhT","Fyefd9mNNorJcZxf9QzcQiQCnlf","MWrGdYifsoQRHjxPuX1cDca1n0g","JoCLdqZYZoOheqxFBYsc00T6nxf","OpeWdDFTYoGWkaxYlFScK8benFg","doxcnABE0zcsAdaA66JTQ2hMKwh","doxcnZVw9g1ZiLJLjiDALPyuA2Q","VgfYdoNO5oy2r6xU5blc0Ds5nih","OMGodMmNSo03b0x8KNfc8Yqmnob","doxcnS0DzPA38pk4rv4CgQuruOd","JEGdd1ERhoAIC9xIsfkchMvhnEd","TStmdWTPwotsDqxZuQMcFFrGnTc","AtH3dXu4koSQ29xf81RcVtk5nEf","ZFrTdmoqxorUNMxljTwcFM8En4e","ZoMCdlLY7o6fwpxtOHycSVXanOf","HKg6d2mmLoa065xvJSEceBaanOe","WHoedU2FHoyQMRx0D7ycB1ELnzh","NAlMdQs4AoIfsqxjavIcYBx5n9d","GpoWdTeyBo9HgaxXwP7c8B7BnTb","EJqYdCvv8ovHnyx7kZ1cmhDtn6d","L6opd8nmKoxF3ExzBcOc6Jc8nfc","L3BfdZQB3oR9nrxWNmJcvwo4nWh","MVLXd91IYochw1xE08lcmckGnvh","LAcZd8c48oDAYyxCmXTcH850nMe","P8w8dFVBZoxIPIxDaoicOfv6nFf","HSFPdt4uOoEs85xbcwbcrCKgniu","M4xXdwatModuKtx7OtHcVLG9ngl","LLGBdXTCCoAqCtxBb0AcFCIWn4g","J3Fgdsj6xoRREJxpBr6cz9A5n5c","OJK8dxH7PoigOdxuIJPcbe5lnhg","XRj5dd82aog1LHxTehOciDWRnoh","IidddrfpboBf7rxXKnUcfaXJnRI","Nf0WdOygRouNlixbV19cJlkjnjh","NYzPdQuFYoPr9Ix2bOjc9qMsnDb","CP4vdqzh2ogonkxI5KNcwZP1n1d","YLf9dExIhohbK9xSkepcgI84nSg","C0JkdZZbuoRgNtxMJDtcXecAn9d","NRZxdH3JNo9MsXxq2Q9cNW1Snlg","HMKadWGCDoOprZxa3sjcqbiFnfg","ZEMId5jQZoGO7nxI5U7coJQ1n1c","VlfNdldOeoktutxsIUEc2ijPnrv","RREzd1IBboGOkQxYzDocHDFInSd","K81PdXWoxoEQYPxvqOucB5fZnOC","HWQ9dPqI3oZ5mMxZcXOc1hN3nWg","NFicdkwaCoNxyhx7oYwcRol0nUd","LeF2dAgJaoZWndxasPzciXCBn1c","TE57dL4ejopsWSxLBs0c0DSRnsc","JQzOdCehvo2EMmxJLkTc0KoWnHd","Dim1drrutokFdqxciTWcZoZOnRb","NEomdel8woQYd1xPhB2chIlSnde","Z5SLdfjqxo6s7Cxpgt4cQ0kInpc","doxcnA30aNa1EpDYnUkAh6HVndg","GkE8dju1qoSIRqxvOwbcyXVPnBg","doxcnjLZEKC39p9PATNZWF1X35f","doxcn1Zj5ukqNEOv8rr69dkJ5Gh","doxcnDENaHmJI7qyYXE5tKcSPwf","doxcnxq3hSC3QoxHsjgmo5qYeHh","ZsemdNRVyozN5dx3vVBc92DRnHd","ItHwdhsx8ofCAXxqTvMczjLOnah","XmZmdoGyOok0TVxXuanc5wSUnqc","HmW2dXdhjooLMxxDXd7ce8PMncg","UvWxdQoHVoCvEDxIvbncT1DknRd","DUTPdMyknoaHWYx2fbEcUmgNnbh"],"text":{"apool":{"nextNum":2,"numToAttrib":{"0":["author","7115054903550050305"],"1":["abbreviation-data","{\"id\":\"1fd3c826-6be1-44d5-85c8-2407a183d57d\",\"abbr_ids\":\"enterprise_7221066159129608193\",\"is_visible\":1,\"is_first\":1}"]}},"initialAttributedTexts":{"attribs":{"0":"*0+1*1*0+2*0+g"},"text":{"0":"【DP/贪心】2023B-观看文艺汇演"}}},"align":"","doc_info":{"editors":["7115054903550050305"],"options":["editors","create_time"],"deleted_editors":null}}}},"payloadMap":{"DzdkdAfLYonVIUxIYkAcWTUHnRh":{"level":1},"Vf62dc38jok8PtxOdsxc1zGFnIe":{"level":1}},"extra":{"mention_page_title":{},"external_mention_url":{}},"isKeepQuoteContainer":false,"selection":[{"id":5,"type":"text","selection":{"start":0,"end":32},"recordId":"DzdkdAfLYonVIUxIYkAcWTUHnRh"},{"id":6,"type":"text","selection":{"start":0,"end":98},"recordId":"Vf62dc38jok8PtxOdsxc1zGFnIe"}],"pasteFlag":"9ea62233-7fdb-4e62-b783-c009066c712d"}" data-lark-record-format="docx/record" class="lark-record-clipboard"></span>

输出描述

<div data-page-id="WyahdwqCLoz0TNxY0Fmc8PUVnSg" data-docx-has-block-data="false"> <div style="white-space-collapse:preserve;" class="ace-line ace-line old-record-id-ZvjKdHzj7o2yiPxK6otcRwtbn0b"> 最多能观看的演出场数。 </div> </div> <span data-lark-record-data="{"rootId":"WyahdwqCLoz0TNxY0Fmc8PUVnSg","text":{"initialAttributedTexts":{"text":{"0":"最多能观看的演出场数。"},"attribs":{"0":"*0+b"}},"apool":{"numToAttrib":{"0":["author","7115054903550050305"]},"nextNum":1}},"type":"text","referenceRecordMap":{},"extra":{"mention_page_title":{},"external_mention_url":{}},"isKeepQuoteContainer":false,"isFromCode":false,"selection":[{"id":8,"type":"text","selection":{"start":0,"end":11},"recordId":"ZvjKdHzj7o2yiPxK6otcRwtbn0b"}],"payloadMap":{},"isCut":false}" data-lark-record-format="docx/text" class="lark-record-clipboard"></span>

示例

示例 1

输入

2
720 120
840 120

输出

1

说明:第一场演出开始时间是第720分钟,经过120分钟演出结束,即第840分钟结束,此时还需要15分钟的间隔时间,即要等到第855分钟才可以看下一场演出,故来不及看第二场在第840分钟开始的演出。最多只能看1场演出。

示例 2

输入

2
20 60
100 60

输出

2

说明:第一场演出开始时间是第20分钟,经过60分钟演出结束,即第80分钟结束,此时还需要15分钟的间隔时间,即要等到第95分钟才可以看下一场演出,第二场演出在第100分钟开始的演出,赶得上观看第二场演出。最多可以观看2场演出。

示例 3

输入

4
10 20
100 20
150 60
80 40

输出

3

时间限制 1000 ms · 内存限制 128 MB

看不懂题目?点开图解
0 720 840 855 1440 演出1 (720~840) 间隔15分钟 演出2 (840~960) 冲突 示例1:最多看1场 演出1结束后需等15分钟,演出2开始时间在间隔内,冲突
写完代码点「提交」,将对全部测试用例判题。

向老师提问

针对「观看文艺汇演」把疑问、代码和报错填清楚,老师收到后能更快、更准地回复你。