Dividir N segmentos en dos grupos no vacíos de modo que se cumpla la condición dada

Dados N segmentos (o rangos) representados por dos números enteros no negativos L y R . Divida estos segmentos en dos grupos no vacíos de modo que no haya dos segmentos de diferentes grupos que compartan un punto común. Si es posible, asigne a cada segmento un número del conjunto {1, 2}; de lo contrario, imprima No es posible .
Ejemplos: 
 

Entrada: arr[][] = {{5, 5}, {2, 3}, {3, 4}} 
Salida: 2 1 1 
Dado que el ^segundo y el ^tercer segmento tienen un punto común, es decir, 3, deben estar contenidos en el mismo grupo.
Entrada: arr[][] = {{3, 5}, {2, 3}, {1, 4}} 
Salida: No es posible 
Todos los segmentos deben estar contenidos en el mismo grupo ya que cada par tiene un punto común entre sí . Dado que el otro grupo está vacío, la respuesta no es posible. 
 

Requisitos previos : fusionar intervalos superpuestos
 

Enfoque: Usando el concepto de fusionar intervalos superpuestos, podemos asignar el mismo grupo a todos aquellos segmentos que se superponen y, alternativamente, cambiar el número de grupo. 
Para fusionar segmentos superpuestos, ordene todos los segmentos con respecto a sus valores izquierdos crecientes, si los valores izquierdos son iguales, ordene primero sobre la base de los valores derechos manteniendo un orden de los índices originales de los segmentos. Luego, itere sobre los segmentos y verifique si alguno de los segmentos anteriores se superpone con el segmento actual. Si lo hace, fusionarlo convirtiéndolo en un segmento y si no crea uno nuevo. 
Por último, compruebe si uno del grupo está vacío o no. Si uno de ellos está vacío, la respuesta no es posible, de lo contrario, imprima todos los valores asignados de los segmentos.
A continuación se muestra la implementación del enfoque anterior:
 

// C++ Program to divide N segments
// into two non empty groups such that
// given condition is satisfied
 
#include<bits/stdc++.h>
using namespace std;
   
// Function to print the answer if
// it exists using the concept of
// merge overlapping segments
void printAnswer(vector<pair<int,int>> v,int n)
{
      // vec[i].first -> left value
      // vec[i].second.first -> right value
      // vec[i].second.second -> position
    vector<pair<int,pair<int,int>>> vec;
    for(int i=0;i<n;i++)
    {
        vec.push_back({v[i].first,{v[i].second,i}});
    }
    sort(vec.begin(),vec.end());
     
 // Resultant array
 //   Initialise all the values in resultant array with '2'
 //   except the position at the first index of sorted vec which is initialised as '1'
 //   Initialise maxR to store the maximum of all right values encountered so far
    vector<int> res(n,2);
    int maxR = vec[0].second.first;
    res[vec[0].second.second] = 1;
 
// If the i-th index has any any point in common with the (i-1)th index classify it as '1'
//    in resultant array and update maxR if necessary
// else we have found the breakpoint and we can exit the loop
     
    bool ok=false;
    for(int i=1;i<n;i++)
    {
        if(maxR>=vec[i].first)
        {
            res[vec[i].second.second] = res[vec[i-1].second.second];
            maxR=max(maxR,vec[i].second.first);
        }
        else
            {
                ok=true;
                break;
            }
    }
    if(ok)
    {
        for(auto x:res)
            cout << x << " ";
        cout << '\n';
    }
    else
        cout << "Not possible\n";
     
}
 
int main()
{
    vector<pair<int,int>> v = {{2,8}, {3,4} , {5,8}, {9,10}};
    int n = (int)v.size();
     
    printAnswer(v,n);
}

# Python3 Program to divide N segments
# into two non empty groups such that
# given condition is satisfied
     
# Function to print the answer if
# it exists using the concept of
# merge overlapping segments
 
def printAnswer(v, n):
    # Sort the indices based on their corresponding value in V   
    indices = list(range(n))
    indices.sort(key=lambda i: v[i])
     
    # Resultant array
    # Initialise all the values in resultant array with '2'
    # except the first index of 'indices' which is initialised as '1'
    # Initialise maxR to store the maximum of all right values encountered so far
    res = [2] * n
    res[indices[0]] = 1
    maxR=v[indices[0]][1]
     
    #If the i-th index has any any point in common with the (i-1)th index classify it as '1' in resultant array and update maxR if necessary
    #else we have found the breakpoint and we can exit the loop   
    for i in range(1, n):
        if maxR>=v[indices[i]][0]:
            res[indices[i]]=res[indices[i-1]]
            maxR=max(maxR,v[indices[i]][1])
        else:
            break
    else:
        print("Not possible")
        return
    print(" ".join(map(str,res)))
     
# Driver Code
if __name__ == "__main__":
 
    v = [[2, 8], [3, 4], [5, 8], [9, 10]]
    n = len(v)
    printAnswer(v, n)

1 1 1 2 

Complejidad Temporal: O(n * log n), donde n es el número de segmentos
Espacio Auxiliar : O(n).