Encuentre el máximo de reuniones en una sala

Hay una sala de reuniones en una empresa. Hay N reuniones en forma de (S[i], F[i]) donde S[i] es la hora de inicio de la reunión i y F[i] es la hora de finalización de la reunión i . La tarea es encontrar el número máximo de reuniones que se pueden acomodar en la sala de reuniones. Imprimir todos los números de reunión

Ejemplos: 

Entrada: s[] = {1, 3, 0, 5, 8, 5}, f[] = {2, 4, 6, 7, 9, 9} 
Salida: 1 2 4 5 
Primera reunión [1, 2] 
Segunda reunión [3, 4] 
Cuarta reunión [5, 7] 
Quinta reunión [8, 9]

Entrada: s[] = {75250, 50074, 43659, 8931, 11273, 27545, 50879, 77924}, 
f[] = {112960, 114515, 81825, 93424, 54316, 35533, 73383, 6 }  160252 
Salida

Enfoque: 
la idea es resolver el problema utilizando el enfoque codicioso, que es lo mismo que el problema de selección de actividades.

• Ordene todos los pares (Reuniones) en orden creciente del segundo número (Hora de finalización) de cada par.
• Seleccione la primera reunión del par ordenado como la primera reunión en la sala y empújela al vector de resultados y establezca un límite de tiempo variable (digamos) con el segundo valor (hora de finalización) de la primera reunión seleccionada.
• Iterar desde el segundo par hasta el último par de la array y si el valor del primer elemento (hora de inicio de la reunión) del par actual es mayor que el tiempo de finalización del par previamente seleccionado (límite_tiempo), seleccione el par actual y actualice el vector de resultados (empuje el número de reunión seleccionado en el vector) y time_limit variable.
• Imprime el orden de la reunión desde el vector.

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

// C++ program to find maximum number of meetings
#include <bits/stdc++.h>
using namespace std;
 
// Function for finding maximum meeting in one room
void maxMeetings(int s[], int f[], int n)
{
    pair<int, int> a[n + 1];
    int i;
    for (i = 0; i < n; i++) {
        a[i].first = f[i];
        a[i].second = i;
    }
    // Sorting of meeting according to their finish time.
    sort(a, a + n);
 
    // Time_limit to check whether new
    // meeting can be conducted or not.
    int time_limit = a[0].first;
 
    // Vector for storing selected meeting.
    vector<int> m;
 
    // Initially select first meeting.
    m.push_back(a[0].second + 1);
 
    // Check for all meeting whether it
    // can be selected or not.
    for (i = 1; i < n; i++) {
        if (s[a[i].second] > time_limit) {
            // Push selected meeting to vector
            m.push_back(a[i].second + 1);
 
            // update time limit
            time_limit = a[i].first;
        }
    }
 
    // Print final selected meetings.
    for (int i = 0; i < m.size(); i++) {
        cout << m[i] << " ";
    }
}
 
// Driver code
int main()
{
    // Starting time
    int s[] = { 1, 3, 0, 5, 8, 5 };
 
    // Finish time
    int f[] = { 2, 4, 6, 7, 9, 9 };
 
    // Number of meetings.
    int n = sizeof(s) / sizeof(s[0]);
 
    // Function call
    maxMeetings(s, f, n);
 
    return 0;
}

// Java program to find maximum number of meetings
import java.util.*;
 
// Comparator function which can compare
// the ending time of the meeting ans
// sort the list
class mycomparator implements Comparator<meeting>
{
    @Override
    public int compare(meeting o1, meeting o2)
    {
        if (o1.end < o2.end)
        {
             
            // Return -1 if second object is
            // bigger then first
            return -1;
        }
        else if (o1.end > o2.end)
         
            // Return 1 if second object is
            // smaller then first
            return 1;
             
        return 0;
    }
}
 
// Custom class for storing starting time, 
// finishing time and position of meeting.
class meeting
{
    int start;
    int end;
    int pos;
     
    meeting(int start, int end, int pos)
    {
        this.start = start;
        this.end = end;
        this.pos = pos;
    }
}
 
class GFG{
     
// Function for finding maximum meeting in one room
public static void maxMeeting(ArrayList<meeting> al, int s)
{
     
    // Initialising an arraylist for storing answer
    ArrayList<Integer> m = new ArrayList<>();
     
    int time_limit = 0;
     
    mycomparator mc = new mycomparator();
     
    // Sorting of meeting according to
    // their finish time.
    Collections.sort(al, mc);
     
    // Initially select first meeting.
    m.add(al.get(0).pos);
     
    // time_limit to check whether new 
    // meeting can be conducted or not.
    time_limit = al.get(0).end;
     
    // Check for all meeting whether it 
    // can be selected or not.
    for(int i = 1; i < al.size(); i++)
    {
        if (al.get(i).start > time_limit)
        {
             
            // Add selected meeting to arraylist
            m.add(al.get(i).pos);
             
            // Update time limit
            time_limit = al.get(i).end;
        }
    }
     
    // Print final selected meetings.
     for(int i = 0; i < m.size(); i++)
        System.out.print(m.get(i) + 1 + " ");
}
 
// Driver Code 
public static void main (String[] args)
{
     
    // Starting time
    int s[] = { 1, 3, 0, 5, 8, 5 };
     
    // Finish time
    int f[] = { 2, 4, 6, 7, 9, 9 }; 
     
    // Defining an arraylist of meet type
    ArrayList<meeting> meet = new ArrayList<>();
    for(int i = 0; i < s.length; i++)
     
        // Creating object of meeting
        // and adding in the list
        meet.add(new meeting(s[i], f[i], i));
         
    // Function call
    maxMeeting(meet, meet.size());
}
}
 
// This code is contributed by Sarthak Sethi

# Python3 program to find maximum number
# of meetings
 
# Custom class for storing starting time,
# finishing time and position of meeting.
class meeting:
     
    def __init__(self, start, end, pos):
         
        self.start = start
        self.end = end
        self.pos = pos
 
# Function for finding maximum
# meeting in one room
def maxMeeting(l, n):
 
    # Initialising an arraylist
    # for storing answer
    ans = []
     
    # Sorting of meeting according to
    # their finish time.
    l.sort(key = lambda x: x.end)
 
    # Initially select first meeting
    ans.append(l[0].pos)
 
    # time_limit to check whether new
    # meeting can be conducted or not.
    time_limit = l[0].end
     
    # Check for all meeting whether it
    # can be selected or not.
    for i in range(1, n):
        if l[i].start > time_limit:
            ans.append(l[i].pos)
            time_limit = l[i].end
             
    # Print final selected meetings
    for i in ans:
        print(i + 1, end = " ")
         
    print()
 
# Driver code
if __name__ == '__main__':
     
    # Starting time
    s = [ 1, 3, 0, 5, 8, 5 ]
 
    # Finish time
    f = [ 2, 4, 6, 7, 9, 9 ]
 
    # Number of meetings.
    n = len(s)
 
    l = []
 
    for i in range(n):
         
        # Creating object of meeting
        # and adding in the list
        l.append(meeting(s[i], f[i], i))
         
    # Function call
    maxMeeting(l, n)
 
# This code is contributed by MuskanKalra1

<script>
 
// JavaScript program to find maximum number of meetings
 
// Function for finding maximum meeting in one room
function maxMeetings(s, f, n)
{   
    //Make an Array : aCollectiveArray like [[index, startTime, endTime]]
    //index will be stored as i + 1, to start indices from 1.
    var aCollectiveArray = [];
    for(var i=0; i<s.length; i++){
        var aNew = [];
        aNew.push(i + 1);
        aNew.push(s[i]);
        aNew.push(f[i]);
        aCollectiveArray.push(aNew);
    }
     
    //array sorted based on end Time
    aCollectiveArray.sort((a,b) => a[2] - b[2]);
     
    //endTime is at 2nd index of subarray inside aCollectiveArray
    var endTime = aCollectiveArray[0][2];
     
    //result will contain the indices of meetings
    var result = [];
     
    //first meeting will be bydefault push as array is already sorted
    result.push(aCollectiveArray[0][0]);
     
    //will compare if next startTime > prev endTime
    for(var k=1; k<aCollectiveArray.length; k++){
        var startTime = aCollectiveArray[k][1];
        if(startTime > endTime){
            result.push(aCollectiveArray[k][0]);
            endTime = aCollectiveArray[k][2]
        }
    }
     
    //If we need to return indices then will return : result
    //or else if we need to return number of meetings then will return result.length
    return result;
}
 
// Driver code
 
 
// Starting time
let s = [ 1, 3, 0, 5, 8, 5 ];
 
// Finish time
let f = [ 2, 4, 6, 7, 9, 9 ];
 
// Number of meetings.
let n = s.length;
 
// Function call
maxMeetings(s, f, n);
 
//This code is contributed by Ankit Kumar.
</script>

Producción: 

1 2 4 5

Complejidad temporal: O(N log(N)) 
Espacio auxiliar: O(N) para crear un vector de pares aproximadamente igual a O(n)