Programación de trabajos con dos trabajos permitidos a la vez

Nos dan N trabajos, y sus tiempos de inicio y finalización. Podemos hacer dos trabajos simultáneamente en un momento determinado. Si un trabajo termina en el mismo momento en que comienza otro programa, entonces no podemos hacerlo. Necesitamos verificar si es posible completar todos los trabajos o no.
Ejemplos: 
 

Input :  Start and End times of Jobs
         1 2 
         2 3
         4 5 
Output : Yes
By the time third job starts, both jobs
are finished. So we can schedule third
job.

Input : Start and End times of Jobs
        1 5
        2 4
        2 6
        1 7
Output : No
All 4 jobs needs to be scheduled at time
3 which is not possible.

Primero ordenamos los trabajos según su hora de inicio. Luego comenzamos dos trabajos simultáneamente y verificamos si el tiempo de inicio del tercer trabajo y así sucesivamente es mayor que el tiempo de finalización de y de los dos trabajos anteriores. 
La implementación de la idea anterior se da a continuación. 
 

// CPP program to check if all jobs can be scheduled
// if two jobs are allowed at a time.
#include <bits/stdc++.h>
using namespace std;
 
bool checkJobs(int startin[], int endin[], int n)
{
    // making a pair of starting and ending time of job
    vector<pair<int, int> > a;
    for (int i = 0; i < n; i++)
        a.push_back(make_pair(startin[i], endin[i]));
 
    // sorting according to starting time of job
    sort(a.begin(), a.end());
 
    // starting first and second job simultaneously
    long long tv1 = a[0].second, tv2 = a[1].second;
 
    for (int i = 2; i < n; i++) {
         
        // Checking if starting time of next new job
        // is greater than ending time of currently
        // scheduled first job
        if (a[i].first >= tv1)
        {
            tv1 = tv2;
            tv2 = a[i].second;
        }
         
        // Checking if starting time of next new job
        // is greater than ending time of currently
        // scheduled second job
        else if (a[i].first >= tv2)
            tv2 = a[i].second;
 
        else
            return false;
    }
    return true;
}
 
// Driver code
int main()
{
    int startin[] = { 1, 2, 4 }; // starting time of jobs
    int endin[] = { 2, 3, 5 }; // ending times of jobs
    int n = sizeof(startin) / sizeof(startin[0]);
    cout << checkJobs(startin, endin, n);
    return 0;
}

# Python3 program to check if all
# jobs can be scheduled if two jobs
# are allowed at a time.
 
def checkJobs(startin, endin, n):
 
    # making a pair of starting and
    # ending time of job
    a = []
    for i in range(0, n):
        a.append([startin[i], endin[i]])
         
    # sorting according to starting
    # time of job
    a.sort()
 
    # starting first and second job
    # simultaneously
    tv1 = a[0][1]
    tv2 = a[1][1]
 
    for i in range(2, n):
         
        # Checking if starting time of next
        # new job is greater than ending time
        # of currently scheduled first job
        if (a[i][0] >= tv1) :
 
            tv1 = tv2
            tv2 = a[i][1]
 
        # Checking if starting time of next
        # new job is greater than ending time
        # of currently scheduled second job
        else if (a[i][0] >= tv2) :
            tv2 = a[i][1]
 
        else:
            return 0
     
    return 1
 
# Driver Code
if __name__ == '__main__':
    startin = [1, 2, 4] # starting time of jobs
    endin = [2, 3, 5] # ending times of jobs
    n = 3
    print(checkJobs(startin, endin, n))
 
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)

Producción: 
 

1

Una solución alternativa es encontrar el número máximo de trabajos que deben programarse en cualquier momento . Si este recuento es más de 2, devuelve falso. De lo contrario, devuelve verdadero.
Este artículo es una contribución de Sarthak Kohli . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.