柳州建設(shè)公司網(wǎng)站,做地方的門戶網(wǎng)站,建立網(wǎng)上商城應(yīng)考慮哪些問(wèn)題,江蘇又一地檢測(cè)出陽(yáng)性2054: 兩個(gè)最好的不重疊活動(dòng)題意#xff1a;在結(jié)束時(shí)間小于 startTime 的活動(dòng)中#xff0c;選擇價(jià)值最大的活動(dòng)。為了方便查找#xff0c;先把 events 按照結(jié)束時(shí)間從小到大排序。排序后#xff0c;對(duì)比如下兩個(gè)活動(dòng)#xff1a;活動(dòng)一#xff1a;結(jié)束于 3 時(shí)刻#xff0…2054: 兩個(gè)最好的不重疊活動(dòng)題意在結(jié)束時(shí)間小于 startTime 的活動(dòng)中選擇價(jià)值最大的活動(dòng)。為了方便查找先把 events 按照結(jié)束時(shí)間從小到大排序。排序后對(duì)比如下兩個(gè)活動(dòng)活動(dòng)一結(jié)束于 3 時(shí)刻價(jià)值 999?；顒?dòng)二結(jié)束于 6 時(shí)刻價(jià)值 9?；顒?dòng)二的結(jié)束時(shí)間又晚價(jià)值又小全方面不如活動(dòng)一是垃圾數(shù)據(jù)直接忽略。換句話說(shuō)在遍歷 events 的過(guò)程中注意 events 已按照結(jié)束時(shí)間排序只在遇到更大價(jià)值的活動(dòng)時(shí)才記錄該活動(dòng)。把這些活動(dòng)記錄到一個(gè)棧列表中那么從棧底到棧頂結(jié)束時(shí)間是遞增的價(jià)值也是遞增的非常適合二分查找。枚舉第二個(gè)活動(dòng)在單調(diào)棧中二分查找結(jié)束時(shí)間嚴(yán)格小于 startTime 的最后一個(gè)活動(dòng)即為價(jià)值最大的第一個(gè)活動(dòng)。如果沒(méi)找到那么只能選一個(gè)活動(dòng)。為了簡(jiǎn)化判斷邏輯可以在棧底加一個(gè)結(jié)束時(shí)間為 0價(jià)值也為 0 的哨兵。ranges::sort(events,{},[](auto e){return e[1];});vectorpairint,int st{{0,0}}; //棧底哨兵auto it--ranges::lower_bound(st,start_time,{},pairint,int::first); ansmax(ans,it-secondvalue);單調(diào)棧遞增如果找不到因?yàn)橛小皸５咨诒币虼苏也坏綕M足條件的活動(dòng)時(shí)it{0,0}it-second0不會(huì)越界。class Solution { public: int maxTwoEvents(vectorvectorint events) { //按照結(jié)束時(shí)間升序排序 ranges::sort(events,{},[](auto e){return e[1];}); //從棧底到棧頂結(jié)束時(shí)間遞增價(jià)值遞增 vectorpairint,int st{{0,0}}; //棧底哨兵 int ans0; for(auto e:events){ int start_timee[0],valuee[2]; //二分查找最后一個(gè)結(jié)束時(shí)間 start_time 的活動(dòng) auto it--ranges::lower_bound(st,start_time,{},pairint,int::first); ansmax(ans,it-secondvalue); if(valuest.back().second) st.emplace_back(e[1],value); } return ans; } };