จำนวนกิจกรรมสูงสุดที่สามารถเข้าร่วมในภาษา C++

สมมติว่าเรามีอาร์เรย์ของเหตุการณ์ที่ events[i] =[startDayi, endDayi] ที่นี่ทุกงานที่ฉันเริ่มต้นที่ startDayi และสิ้นสุดที่ endDayi เราสามารถเข้าร่วมกิจกรรม I ได้ทุกวัน d โดยที่ d อยู่ในช่วง startTimei และ endTimei (รวมทั้งสองอย่าง) เราต้องจำไว้ว่าเราสามารถเข้าร่วมได้ครั้งละหนึ่งงานเท่านั้น ดังนั้นจงหาจำนวนกิจกรรมสูงสุดที่เราสามารถเข้าร่วมได้ ตัวอย่างเช่น หากอินพุตเป็น [[1,4], [4,4], [2,2], [3,4], [1,1]] ผลลัพธ์จะเป็น 1 ตามที่เรา สามารถเข้าร่วมได้สูงสุด 4 กิจกรรม ได้แก่ [1, 1], [2, 2], [3, 4] และ [4, 4]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=จำนวนเหตุการณ์ จากนั้นเรียงลำดับรายการเหตุการณ์ตามวันที่เริ่มต้น ตั้งค่า ret :=0 และ itr :=0

• สร้างคิวลำดับความสำคัญตาม max-heap ที่เรียกว่า pq

• สำหรับผมอยู่ในช่วง 1 ถึง 10,000

  • ในขณะที่ itr

    • แทรกเหตุการณ์[itr, 1]

    • เพิ่มขึ้นอีก 1

  • ในขณะที่ pq ไม่ว่างและด้านบนของ pq

    • ลบองค์ประกอบออกจาก pq

  • ถ้า pq ไม่ว่าง ให้ลบออกจาก pq และเพิ่ม ret ขึ้น 1

• รีเทิร์น

ตัวอย่าง (C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   static bool cmp(vector <int>& a, vector <int>& b){
      return a[0] < b[0];
   }
   int maxEvents(vector<vector<int>>& events) {
      int n = events.size();
      sort(events.begin(), events.end(), cmp);
      int ret = 0;
      int itr = 0;
      priority_queue <int, vector <int>, greater <int>> pq;
      for(int i = 1; i <= 1e5; i++){
         while(itr < n && events[itr][0] == i){
            pq.push(events[itr][1]);
            itr++;
         }
         while(!pq.empty() && pq.top() < i) pq.pop();
         if(!pq.empty()){
            pq.pop();
            ret++;
         }
      }
      return ret;
   }
};
main(){
   vector<vector<int>> v = {{1,4},{4,4},{2,2},{3,4},{1,1}};
   Solution ob;
   cout << (ob.maxEvents(v));
}

อินพุต

[[1,4],[4,4],[2,2],[3,4],[1,1]]

ผลลัพธ์

4