/*
 * 19MF3IM05 - Kumar Sambhaw
 * Class Test - 1
 */

#include <cmath>
#include <cstring>
#include <iostream>

using namespace std;

//  Merge Sort algorithm modified to suit this problem, to sort a 2D array/list
void merge(int arr[][2], int n, int l, int r) // merge() function to merge the sub-arrays
{
    int mid = (l + r) >> 1;
    int arr1[mid - l + 1][2], arr2[r - mid][2];
    for (int i = l; i <= mid; i++)
    {
        arr1[i - l][0] = arr[i][0];
        arr1[i - l][1] = arr[i][1];
    }
    for (int i = mid + 1; i <= r; i++)
    {
        arr2[i - mid - 1][0] = arr[i][0];
        arr2[i - mid - 1][1] = arr[i][1];
    }
    int i = 0, j = 0;
    int l1 = mid - l + 1;
    int l2 = r - mid;
    int idx = l;

    // merge
    while (i < l1 && j < l2)
    {
        if (arr1[i][1] < arr2[j][1])
        {
            arr[idx][0] = arr1[i][0];
            arr[idx][1] = arr1[i][1];
            i++;
        }
        else
        {
            arr[idx][0] = arr2[j][0];
            arr[idx][1] = arr2[j][1];
            j++;
        }
        idx++;
    }
    // exhaustive filling to complete merge
    while (i < l1)
    {
        arr[idx][0] = arr1[i][0];
        arr[idx][1] = arr1[i][1];
        i++;
        idx++;
    }
    while (j < l2)
    {
        arr[idx][0] = arr2[j][0];
        arr[idx][1] = arr2[j][1];
        j++;
        idx++;
    }
}

void mergesort(int arr[][2], int n, int l, int r)
{
    if (l >= r)
        return;
    int mid = (l + r) >> 1;
    mergesort(arr, n, l, mid);
    mergesort(arr, n, mid + 1, r);
    merge(arr, n, l, r);
}
// ---------------------------------------------------------------------

// to check if there's a collision/overlapping between the objects/event in the cycle.
bool isnotcollide(int a[2], int b[2])
{
    if (a[0] <= a[1] && b[0] <= b[1])
    {
        return b[0] > a[1];
    }
    if (a[0] <= a[1] && b[0] > b[1])
    {
        return b[0] > a[1] && b[1] < a[0];
    }
    if (a[0] > a[1] && b[0] <= b[1])
    {
        return a[0] > b[1] && a[1] < b[0];
    }
    return false;
}

/*
    Greedy Algorithm: Sort by the second index, i.e. the finish angle, (finish times)
    then select each item one at a time
    and do a linear pass to calculate the answer.

    Time Complexity: O(n^2) + O(nlogn) => O(n*n) or O(n^2)
                   {Greedy}  {mergesort}
*/

// greedy algorithm involving a linear pass after selection of one item at a time
int calc(int arr[][2], int n, int i, bool s[])
{
    int ans = 0;
    int prev = -1;
    int first = -1;
    for (int x = 0; x < n; x++) // linear pass O(n)
    {
        int idx = (x + i) % n;
        if (prev < 0 || (isnotcollide(arr[prev], arr[idx]) &&
                         isnotcollide(arr[first], arr[idx]))) // if no collision
        {
            prev = idx;
            if (first < 0)
                first = idx;
            ans++;
            s[idx] = 1;
        }
        else
            s[idx] = 0;
            
    }
    return ans;
}

int main() // to control program execution
{
    int n;
    cout << "Write the number of objects: ";
    cin >> n;

    cout << "Write the start and end angles of "<< n <<" objects:" << endl;
    int arr[n][2];
    for (int i = 0; i < n; i++)
    {
        cout << "start=";
        cin >> arr[i][0];
        cout << "end=";
        cin >> arr[i][1];
    }

    // sort on the basis of the second index.
    mergesort(arr, n, 0, n - 1);

    int ans = 0;
    bool sel[n];
    bool ans_sel[n]; // stores if an object is to be selectied or not.
    for (int i = 0; i < n; i++)
    {
        int v = calc(arr, n, i, sel); // linear pass greedy algorithm executed under loop
        if (ans < v)
        {
            ans = v;
            memcpy(ans_sel, sel, sizeof(sel)); // copy sel into ans_sel
        }
    }

    // Result:
    cout << "\nMaximum number of objects: " << ans << '\n';
    cout << "Objects Selected:" << endl;
    for (int i = 0; i < n; i++)
    {
        if (ans_sel[i]) // check if an object is included
        {
            cout << "start=" << arr[i][0] << " end=" << arr[i][1] << '\n';
        }
    }
}