সি++-এ ব্যানার হ্যাঙ্গ করার জন্য ন্যূনতম পিন সংখ্যা বের করা

সমস্যা বিবরণ

ব্যানারের ইন্টারভ্যাল [start, end] দেওয়া আছে। কমপক্ষে একটি পিন লাগে একটি ব্যানার হ্যাঙ্গ করতে। একটি পিন একাধিক ব্যানার হ্যাঙ্গ করতে পারে। সব ব্যানার হ্যাঙ্গ করার ন্যূনতম পিন সংখ্যা বের করতে হবে।

উদাহরণ: intervals = [[2,5],[5,6],[8,10],[10,13]] → আউটপুট 2। পিন ৫ এবং ১০-এ দিলে সব ব্যানার হ্যাঙ্গ হয়।

সমাধানের পদ্ধতি

গ্রিডি অ্যালগরিদম (ইন্টারভ্যাল শিডিউলিং):

1. ইন্টারভ্যালগুলো end অনুযায়ী সর্ট করুন।
2. last = -INF ইনিশিয়ালাইজ করুন।
3. প্রতিটি ইন্টারভ্যালের জন্য: যদি last >= start হয় তবে ইতিমধ্যে কভারড → স্কিপ করুন।
4. অন্যথায় নতুন পিন লাগবে: ret++, last = end।
5. এটি আপ্টিমাল কারণ সবচেয়ে আগে শেষ হওয়া ইন্টারভ্যাল কভার করলে সর্বোচ্চ ভবিষ্যতের ইন্টারভ্যাল কভার হয়।

উদাহরণ কোড

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b) {
        return a.back() < b.back();
    }
    int solve(vector<vector<int>>& v) {
        sort(v.begin(), v.end(), cmp);
        int ret = 0, last = -1e8;
        for (auto& it : v) {
            if (last >= it[0]) continue;
            ret++;
            last = it[1];
        }
        return ret;
    }
};

int main() {
    vector<vector<int>> v = {{2,5},{5,6},{8,10},{10,13}};
    cout << solve(v);
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: {{2,5},{5,6},{8,10},{10,13}}

আউটপুট: 2