#include <set>
#include <list>
#include <algorithm>
#include <string>
#include <iostream>
#include <fstream>
#include <map>

#define INICIO true
#define FIM false

using namespace std;

typedef pair<int, int> Interval;

// Mapa da coloração dos intervalos
// Usa-se ponteiro de intervalo para economizar memória
// (C++ por padrão cria uma cópia do objeto)
typedef map<Interval*, int> Coloring;

class IntervalExtremity {
    public:
        int time;
        Interval* interval;
        bool position; // INICIO ou FIM

        IntervalExtremity(int time, Interval *interval, bool position) {
            this->time = time;
            this->interval = interval;
            this->position = position;
        }

        // Comparador para ordenação
        bool operator< (const IntervalExtremity &other) const {
            return this->time < other.time;
        }
};

list<IntervalExtremity> read(string filename) {

    list<IntervalExtremity> extremities;

    ifstream file(filename.c_str(), ifstream::in );

	if (!file.is_open())
	{
		cout << "Arquivo nao encontrado!" << endl;
		exit(0);
	}

    int inicio, fim;
    while(file >> inicio >> fim) {
        Interval* interval = new Interval(inicio, fim);

        IntervalExtremity int_inicio(inicio, interval, INICIO);
        IntervalExtremity int_fim(fim, interval, FIM);
        extremities.push_back(int_inicio);
        extremities.push_back(int_fim);
    }

	extremities.sort();

	return extremities;
}

Coloring color(list<IntervalExtremity> &extremities) {

    Coloring coloring;
    // Conjunto das cores livres. As cores são criadas sob demanda.
    // set é uma estrutura de dados (otimizada) nativamente ordenada.
    set<int> freeColors;
    int maxColor = 0;

    // Itera todas as extremidades
    list<IntervalExtremity>::iterator it;
    for (it = extremities.begin(); it != extremities.end(); ++it) {

        // Se for início de intervalo, pega a menor
        // cor do conjunto das cores livres
        if ( (*it).position == INICIO ) {
            set<int>::iterator itColor;
            itColor = freeColors.begin();
            int color;

            // Caso não tenha mais cores no conjunto, cria uma nova.
            if (itColor == freeColors.end()) {
                maxColor++;
                color = maxColor;
            } else {
                color = *itColor;
                freeColors.erase(itColor);
            }

            coloring[((*it).interval)] = color;
        } else {
            int color = coloring[(*it).interval];
            freeColors.insert(color);
        }
    }
    return coloring;
}

int main(int argv, char *argc[]) {

    if(argv < 2) {
        cout << "Argumento faltando!" << endl;
        return 1;
    }

    list<IntervalExtremity> extremities = read(argc[1]);

    Coloring coloring = color(extremities);

    Coloring::iterator it;
    for (it = coloring.begin(); it != coloring.end(); ++it) {
        cout << (*it).first->first << " - " << (*it).first->second << " = " << (*it).second << endl;
    }

    return 0;
}