There are A number of days in a year. And you have to perform some type of work in a year. There are M types of work to be performed. And you are given a 2D array B of size M which represents the description for the different types of work.

B[i][0] means the day on which the ith work is given. B[i][1] means the ith work must be completed before this day. B[i][2] denotes teh number of days it will take to complete ith work.

Now, on any day, one of these three things can be done — 1. Rest day 2. This is the deadline date for any work (i.e B[i][1]) (nothing can be done on this day) 3. You are performing any one work

If in case you cannot perform all work before the deadline return a vector of size 1 which is [-1] Else return av ector of size A + 1 whose first element is — 1 and the - ith element is 0 if it is a rest day. - ith elment is M + 1 if this day is a deadline for any type of work. - if any type of work is performed on this day then the ith element will be the type of that work. (Types are starting from 1 to m)

Note — On any day there will be a deadline for a most 1 type of work. If more than one type of work can be performed on any day then perform the one having a deadline first.

Problem Constraints: 2 <= A <= 100 1 <= M <= A 1 <= B[i][0] <= B[i][1] <= A 1 <= B[i][2] <= A

The basic idea of my solution is to follow a greedy approach and just try to implement what is given. First marks all the days that are deadlines to certain work with M + 1. They cannot be used anywhere. Then store iterate from day 1 to A. Maintain a minimum priority queue of works that can be done on this day. That is works that have start day on or before this day. Now take the day with smallest deadline(as given in the question) and remove it from priority queue and assign day to this work. Decrease this days duration and if it's still greater than 0 push it back into priority queue.

#include <bits/stdc++.h>
 
using namespace std;
 
//#pragma GCC optimize("Ofast,unroll-loops") 
//#pragma GCC target("avx,avx2,avx512,fma") 
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
 
#define ll long long
#define ld long double
 
#define PI 3.1415926535897932384626433832795l 

// -------------------------<rng>------------------------- 
// RANDOM NUMBER GENERATOR
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());  
#define SHUF(v) shuffle(all(v), RNG); 
// Use mt19937_64 for 64 bit random numbers.
 
 
#define pii  pair<int, int>
vector<int> solve(int A, vector<vector<int>> &b){
    int m = b.size();
    vector<int> start(m + 1), end(m + 1), dur(m + 1);
    for(int i = 0; i < m; ++i){
        start[i + 1] = b[i][0];
        end[i + 1] = b[i][1];
        dur[i + 1] = b[i][2];
    }
    priority_queue<pii, vector<pii>, greater<pii>> pqs, pqe;
    for(int i = 1; i <= m; ++i){
        pqs.push({start[i], i});
    }
    vector<int> ans(A + 1);
    ans[0] = -1;
    bool isPossible = true;
    for(int day = 1; day <= A; ++day){
        while(!pqs.empty() && (pqs.top().first <= day)){
            int id, _;
            tie(_, id) = pqs.top();
            pqs.pop();
            pqe.push({end[id], id});
        }
        if(ans[day] == m + 1){
            continue;
        }
        if(!pqe.empty()){
            int id, _;
            tie(_, id) = pqe.top();
            pqe.pop();
            ans[day] = id;
            if(end[id] < day){
                isPossible = false;
                break;
            }
            --dur[id];
            if(dur[id] == 0){
                pqe.push({end[id], id});
            }
        }
    }
    if(!pqe.empty() || !pqs.empty()){
        isPossible = false;
    }
    if(!isPossible){
        ans.assign(1, -1);
    }
    return ans;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    int A, M;
    cin >> A >> M;
    vector<vector<int>> B(M, vector<int>(3));
    for(int i = 0; i < M; ++i){
        cin >> B[i][0] >> B[i][1] >> B[i][2];
    }
    for(int elem : solve(A, B)){
        cout << elem << ' ';
    }
    cout << '\n';
    
    return 0;
}
 

C. You are given an integer A and an integer array B, which is the permutation of A integers. Now, you have to perform some swap poerations on this permutation B. Now, after this swap operation B should be such that it can be made to identity permutation by exactly C swaps (which is minimum required)

You have to return a 2D array D which denotes the minimum swaaps you have to perform so that B will become identity after exactly C swaps. D[i][0] adn D[i][1] deontes the index of swap operation you are performing. Return the lexicographically smallest array D.

If you don't need to perform any swap operation then return D = -1, -1

Note — Identity permutation is a permutation where B[i] = i, for each 1 <= i <= A

Problem Constraints: 1 <= A <= 3000 0 <= C < A

#include <bits/stdc++.h>
 
using namespace std;
 
//#pragma GCC optimize("Ofast,unroll-loops") 
//#pragma GCC target("avx,avx2,avx512,fma") 
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
 
#define ll long long
#define ld long double
 
#define PI 3.1415926535897932384626433832795l 

// -------------------------<rng>------------------------- 
// RANDOM NUMBER GENERATOR
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());  
#define SHUF(v) shuffle(all(v), RNG); 
// Use mt19937_64 for 64 bit random numbers.
 
vector<vector<int>> getCycles(vector<int> &p){
    int n = p.size();
    vector<bool> vis(n);
    vector<int> ind(n);

    for(int i = 0; i < n; ++i){
        --p[i];
        ind[p[i]] = i;
    }

    vector<vector<int>> cycles;
    for(int i = 0; i < n; ++i){
        if(vis[i]){
            continue;
        }
        int cur = i;
        vector<int> c;
        while(!vis[cur]){
            vis[cur] = true;
            c.push_back(cur);
            cur = ind[cur];
        }
        cycles.push_back(c);
    }
    for(auto &c : cycles){
        for(auto &ind : c){
            ++ind;
        }
    }
    return cycles;
}
 
vector<vector<int>> solve(vector<int> &p, int k) {
    int n = p.size();
    vector<vector<int>> ans;
    // all cycles cycles
    vector<vector<int>> cycles = getCycles(p);

    // req cycles
    int req_cycles = n - k;
    int no_cycles = cycles.size();
    if(req_cycles < no_cycles){
        ll diff = cycles.size() - req_cycles;
        priority_queue<int, vector<int>, greater<int>> pq;
        for(auto c : cycles){
            pq.push(c.front());
        }
        while(diff--){
            int u = pq.top();
            pq.pop();
            int v = pq.top();
            pq.pop();
            ans.push_back({u, v});
            pq.push(u);
        }
    }
    else if(req_cycles > no_cycles){
        while(!cycles.empty()){
            vector<int> c = cycles.back();
            cycles.pop_back();
            if(c.size() == 1){
                continue;
            }
            if(c.size() == 2){
                ans.push_back({c[0], c[1]});
                continue;
            }
            int mn_ind = min_element(c.begin() + 1, c.end()) - c.begin();
            ans.push_back({c[0], c[mn_ind]});
            vector<int> c1, c2;
            c1.push_back(c[0]);
            for(int i = mn_ind + 1; i < no_cycles; ++i){
                c1.push_back(c[i]);
            }
            c2.push_back(c[mn_ind]);
            for(int i = 1; i < mn_ind; ++i){
                c2.push_back(c[i]);
            }
            cycles.push_back(c1);
            cycles.push_back(c2);
        }
        int diff = req_cycles - no_cycles;
        sort(ans.begin(), ans.end());
        ans.resize(diff);
    }
    if(ans.empty()){
        ans = {{-1, -1}};
    }
    return ans;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    for(int i = 0; i < n; ++i){
        cin >> p[i];
    }
    for(auto v : solve(p, k)){
        cout << v[0] << ' ' << v[1] << '\n';
    }
    
    return 0;
}
 

You are given an 2D array A which indicates |A| segments covered. ith segment cover integer points from A[i][0] to A[i][1] inclusive.

Now, your task is to find the number of integer points that are covered by exactly i number of segments for each 1 <= i <= |A|.

Return an arrray B of size |A| + 1, where B[i] denotes the number of integer points that are covered by exactly i segments.

Note: B[0] must be equal to 0.

Problem Constraints 1 <= |A| <= 2 * (10 ** 5) 0 <= A[i][0] <= A[i][1] <= 10 ** 18

#include <bits/stdc++.h>
 
using namespace std;
 
//#pragma GCC optimize("Ofast,unroll-loops") 
//#pragma GCC target("avx,avx2,avx512,fma") 
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
 
#define ll long long
#define ld long double
 
#define PI 3.1415926535897932384626433832795l 

// -------------------------<rng>------------------------- 
// RANDOM NUMBER GENERATOR
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());  
#define SHUF(v) shuffle(all(v), RNG); 
// Use mt19937_64 for 64 bit random numbers.
 
 
vector<ll> solve(vector<vector<ll>> &a) {
    int n = a.size();
    vector<ll> ans(n + 1);
    map<ll, ll> points;

    for(auto &v : a){
        ll l = v[0], r = v[1];
        ++points[l];
        --points[r + 1];
    }
    ll cur_points = 0;
    ll prev_ind = -1;
    for(auto [ind, p] : points){
        if(cur_points > 0){
            ans[cur_points] += ind - prev_ind;
        }
        prev_ind = ind;
        cur_points += p;
    }
    return ans;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector<vector<ll>> a(n);
    for(int i = 0; i < n; ++i){
        ll l, r;
        cin >> l >> r;
        a[i] = {l, r};
    }
    for(auto u : solve(a)){
        cout << u << ' ';
    }

    return 0;
}