Haga que los intervalos no se superpongan asignándolos a dos procesadores diferentes

Dada una lista de intervalos interval[] donde cada intervalo contiene dos números enteros L y R , la tarea es asignar intervalos a dos procesadores diferentes de modo que no haya intervalos superpuestos para cada procesador. Para asignar el intervalo[i] al primer procesador, imprima “F” y para asignarlo al segundo procesador, imprima “S”.
Nota: Si no hay solución posible, imprima -1.
Ejemplos: 
 

Entrada: intervalo[] = {{360, 480}, {420, 540}, {600, 660}} 
Salida: S, F, S 
Explicación: 
Los intervalos asignados a los procesadores son: 
Intervalos del primer procesador {{420, 540 }} 
Intervalos del segundo procesador {{360, 480}, {600, 660}} 
Como no hay intervalos superpuestos para cada procesador, será una solución válida.
Entrada: intervalo[] = {{99, 150}, {1, 100}, {100, 301}, {2, 5}, {150, 250}} 
Salida: S, F, F, S, S 
Explicación: 
Los intervalos asignados a los procesadores son: 
Intervalos del primer procesador {{1, 100}, {100, 301}} 
Intervalos del segundo procesador {{99, 150}, {2, 5}, {150, 250}} 
Como no hay intervalos superpuestos para cada procesador, será una solución válida. 
 

Enfoque: La idea es usar el algoritmo Greedy para asignar los intervalos al procesador. 
Si el tiempo de finalización más alto del procesador es menor o igual que el tiempo de inicio de un intervalo, este intervalo se puede asignar al procesador. De lo contrario, busque el otro procesador. Si no se puede asignar ningún intervalo a ningún procesador, no hay solución posible. 
A continuación se muestra la ilustración de los pasos del enfoque: 
 

• Como en el problema actual, tenemos que imprimir según el orden de los intervalos. Entonces, para guardar el orden de los intervalos, empareje los intervalos con su índice.
• Ordena los intervalos por su hora de inicio. es decir , L.
• Iterar sobre los intervalos y asignar los intervalos a los procesadores de la siguiente manera: 
   

if (interval[i][0] >= firstProcessorEndTime)
    answer[interval[i]] = "F"
    firstProcessorEndTime = 
        max(firstProcessorEndTime, interval[i][0])
else if (interval[i][0] >= secondProcessorEndTime)
    answer[interval[i]] = "S"
    secondProcessorEndTime = 
        max(secondProcessorEndTime, interval[i][0])
else
    print(-1)

A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation for intervals
// scheduling to two processors such
// that there are no overlapping intervals
#include <bits/stdc++.h>
using namespace std;
 
// Function to assign the intervals
// to two different processors
void assignIntervals(vector<vector<int> > interval, int n)
{
 
    //  Loop to pair the interval
    //  with their indices
    for (int i = 0; i < n; i++)
        interval[i].push_back(i);
 
    // sorting the interval by
    // their start times
    sort(interval.begin(), interval.end());
 
    int firstEndTime = -1;
    int secondEndTime = -1;
    char find = ' ';
    bool flag = false;
 
    // Loop to iterate over the
    // intervals with their start time
    for (int i = 0; i < n; i++) {
        if (interval[i][0] >= firstEndTime) {
            firstEndTime = interval[i][1];
            interval[i].push_back('S');
        }
        else if (interval[i][0] >= secondEndTime) {
            secondEndTime = interval[i][1];
            interval[i].push_back('F');
        }
        else {
            flag = true;
            break;
        }
    }
 
    // Condition to check if there
    // is a possible solution
    if (flag)
        cout << (-1);
    else {
        vector<char> form(n, ' ');
 
        for (int i = 0; i < n; i++) {
            int indi = interval[i][2];
            form[indi] = interval[i][3];
        }
 
        // form = ''.join(form)
        for (int i = 0; i < form.size(); i++)
            cout << form[i] << ",";
    }
}
 
// Driver Code
int main()
{
 
    vector<vector<int> > intervals
        = { { 360, 480 }, { 420, 540 }, { 600, 660 } };
 
    // Function Call
    assignIntervals(intervals, intervals.size());
    return 0;
}

# Python implementation for intervals
# scheduling to two processors such
# that there are no overlapping intervals
 
# Function to assign the intervals
# to two different processors
def assignIntervals(interval, n):
     
    # Loop to pair the interval
    # with their indices
    for i in range(n):
        interval[i].append(i)
         
    # sorting the interval by
    # their startb times
    interval.sort(key = lambda x: x[0])
     
    firstEndTime = -1
    secondEndTime = -1
    find = ''
    flag = False
     
    # Loop to iterate over the
    # intervals with their start time
    for i in range(n):
        if interval[i][0] >= firstEndTime:
            firstEndTime = interval[i][1]
            interval[i].append('S')
        elif interval[i][0] >= secondEndTime:
            secondEndTime = interval[i][1]
            interval[i].append('F')
        else:
            flag = True
            break
     
    # Condition to check if there
    # is a possible solution
    if flag:
        print(-1)
    else:
        form = ['']*n
        for i in range(n):
            indi = interval[i][2]
            form[indi] = interval[i][3]
        # form = ''.join(form)
        print(form, ", ")
 
# Driver Code   
if __name__ == "__main__":
    intervals = [[360, 480], [420, 540], [600, 660]]
     
    # Function Call
    assignIntervals(intervals, len(intervals))

['S', 'F', 'S'] ,

Complejidad temporal: O(NlogN)
Espacio auxiliar: O(N)