ENCNOV4-Editorial

editorial
, ,
1

PROBLEM LINK:

Practice

Author: Abhijeet Trigunait
Tester: Sandeep Singh, Arnab Chanda
Editorialist: Abhijeet Trigunait

DIFFICULTY:

EASY

PREREQUISITES:

Greedy

PROBLEM:

Given some sets of intervals , for each set, find the maximum number of disjoint intervals.

EXPLANATION:

we need to observe that the intervals in different sets are independent (in the original statement, the events preferred in different rooms are independent).
For a single set, it is a classical greedy problem.

  1. Sort the intervals by their right end ascending.
  2. Initialized the select intervals as an empty set
  3. Consider the sorted intervals one by one, add it if it is possible (only need to check the last select interval and the current one).Check last interval end time with current interval start time.

we can solve this problem in O( N log N ), where N is the total number of intervals in all sets

SOLUTIONS:

Solution 
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstdlib>
#include<climits>
#include<cstring>
#define lld long long int
#define F first
#define S second
#define P pair<int,int>
#define pb push_back
#define mod 1e9+7
#define setbits(x) __builtin_popcountll(x)
#define zerobits(x) __builtin_ctzll(x)
#define gcd(x,y) __gcd(x,y)
#define endl '\n'
using namespace std;



lld getMax(vector<pair<lld, lld>> vec) {
    lld siz = vec.size();
    if(siz==0){
        return 0;
    }
    sort(vec.begin(), vec.end());
    lld res = vec[0].first;
    lld count = 1;
    for (lld i = 1; i < siz; ++i) {
  	    if (vec[i].second >= res) {
		    ++count;
		    res = vec[i].first;
	    }
    }
    return count;

}


int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lld t;
    cin >> t;
    while (t--) {
        vector<pair<lld, lld>> rest[1000005];
        map<lld, lld> mp;
	    lld n, box, pos = 0;
	    cin >> n >> box;
	    mp.clear();
	    if(n==0){
	        cout<<"0"<<endl;
	        continue;
	    }
	    for(lld i=0;i<=n;++i)
	    rest[i].clear();
	    lld temp = n;
	    while (temp--) {
		    lld start, end, comp;
		    cin >> start >> end >> comp;
		    comp--;
		    if (mp.count(comp) == 0) {
			    mp[comp] = pos++;
		    }
		    rest[mp[comp]].pb(make_pair(end,start));
	    } lld ans = 0;
	    for (lld i = 0; i < pos; ++i) {
		    ans +=getMax(rest[i]);
	    }
	    cout << ans << endl;

    }
}