fgfs.cpp

#include <iostream>
using namespace std;

void swap(int &x, int &y)
{
    int t = x;
    x = y;
    y = t;

    return ;
}

void sort1(int s[], int f[], int p[], int n)
{
    for(int i=0;i<n-1;i++)
    {
        int min = i;
        for(int j=i+1;j<n;j++)
            if(p[j]<p[min])
                min = j;
        swap(s[i],s[min]);
        swap(f[i],f[min]);
        swap(p[i],p[min]);
    }

    return ;
}

void sort2(int s[], int f[], int l, int r)
{
    for(int i=l;i<r-1;i++)
    {
        int min = i;
        for(int j=i+1;j<r;j++)
            if(f[j]<f[min])
                min = j;
        swap(s[i],s[min]);
        swap(f[i],f[min]);
    }

    return ;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n,k;
        cin >> n >> k;

        int s[n],f[n],p[n];
        int comp[k+1] = {};

        for(int i=0;i<n;i++)
        {
            cin >> s[i] >> f[i] >> p[i];
            comp[p[i]]++;
        }

        sort1(s,f,p,n);

        int count = 0;
        int i=0;
        while(i<n)
        {
            int l = i;
            int r = i+comp[p[i]];
            sort2(s,f,l,r);

            count++;
            int j = l;
            for(int k = l+1;k<r;k++)
            {
                if(s[k]>=f[j])
                {
                    count++;
                    j = k;
                }
            }
            i = r;
        }
        cout << count << endl;
    }
    return 0;
}