Encuentre el tiempo necesario para finalizar el procesamiento de procesos dados

Dados N procesos y dos arreglos, arr1[] y arr2[] de tamaño N cada uno. arr1[] contiene el tiempo empleado por cualquier proceso en la sección crítica y arr2[] indica el tiempo que tarda un proceso en completar el procesamiento después de salir de la sección crítica. La tarea es encontrar el tiempo que tardan todos los procesos en completar su procesamiento (tanto en la sección crítica como fuera de la sección crítica) si se procesan en cualquier orden.

Nota: No pueden estar dos procesos utilizando la sección crítica en el mismo instante de tiempo, pero se puede procesar más de un proceso en el mismo instante de tiempo fuera de la sección crítica.

Ejemplos:

Entrada: N = 3, arr1[] = {1, 4, 3}, arr2[] = {2, 3, 1}
Salida: 9
Explicación:
El primer proceso: entra en la sección crítica en el tiempo 0. 
Entonces, después de 1 unidad vez que completa la tarea de la sección crítica y toma 2 unidades más fuera de la sección crítica. 
Entonces, el tiempo total después del cual finaliza el primer proceso es de 3 unidades.
El segundo proceso: después de 1 unidad de tiempo entra en la sección crítica y sale de la sección crítica después de la 5ª unidad. 
Luego pasa 3 unidades de tiempo fuera de la sección crítica y finalmente termina después de la 8ª unidad de tiempo.
El 3er proceso: Después de 5 unidades de tiempo accede a la sección crítica y sale después de la 8ª unidad de tiempo. 
Luego pasa 1 unidad más fuera de la sección crítica y se termina después de 9 unidades de tiempo desde el inicio de todos los procesos.
Así que el tiempo total empleado es 9

Entrada: N = 2, arr1[] = {2, 1}, arr2[] = {5, 2}
Salida: 7

Enfoque: La solución al problema se basa en el concepto de clasificación . Sigue los pasos:

• Almacene el arr1[i] y el arr2[i] en una lista y aplique la ordenación.
• Ordenar sobre la base de arr2[i] .
• Mantener una variable que almacene el tiempo máximo que tardarán los procesos en terminar de procesarse.

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

// C++ program to implement the approach
#include <bits/stdc++.h>
using namespace std;
 
// Comparator for sorting the vector of pair
static bool comp(pair<int, int> p1,
                 pair<int, int> p2)
{
    return p1.second > p2.second;
}
 
// Function to find the total time taken
int solution(int arr1[], int arr2[], int N)
{
    vector<pair<int, int> > v;
 
    // Store all the arr1[i] and arr2[i]
    // as pair in vector
    for (int i = 0; i < N; i++)
        v.push_back({ arr1[i], arr2[i] });
 
    // Sort based on time spent
    // outside critical section (arr2[])
    sort(v.begin(), v.end(), comp);
    int geek = 0, ans = 0;
 
    // Loop to calculate total time
    for (int i = 0; i < N; i++) {
        geek += v[i].first;
        ans = max(ans, geek + v[i].second);
    }
    return ans;
}
 
// Driver code
int main()
{
    int arr1[] = { 1, 4, 3 };
    int arr2[] = { 2, 3, 1 };
    int N = sizeof(arr1) / sizeof(arr1[0]);
 
    // Function call
    cout << solution(arr1, arr2, N);
    return 0;
}

// Java program to implement the approach
import java.util.*;
 
class GFG{
 
// Comparator for sorting the vector of pair
    static class pair implements Comparable<pair>
    {
        int first,second;
        pair(int s, int e)
        {
            first = s;
            second = e;
        }
          
        public int compareTo(pair p)
        {
            return p.second - this.second;
        }
    }
 
// Function to find the total time taken
static int solution(int arr1[], int arr2[], int N)
{
    Vector<pair > v = new Vector<pair >();
 
    // Store all the arr1[i] and arr2[i]
    // as pair in vector
    for (int i = 0; i < N; i++)
        v.add(new pair( arr1[i], arr2[i] ));
 
    // Sort based on time spent
    // outside critical section (arr2[])
    Collections.sort(v);
    int geek = 0, ans = 0;
 
    // Loop to calculate total time
    for (int i = 0; i < N; i++) {
        geek += v.get(i).first;
        ans = Math.max(ans, geek + v.get(i).second);
    }
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    int arr1[] = { 1, 4, 3 };
    int arr2[] = { 2, 3, 1 };
    int N = arr1.length;
 
    // Function call
    System.out.print(solution(arr1, arr2, N));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program to implement the approach
 
# Comparator for sorting the vector of pair
from functools import cmp_to_key
 
def comp(p1, p2):
    return p1[0] - p2[1]
 
# Function to find the total time taken
def solution(arr1, arr2, N):
    v = []
 
    # Store all the arr1[i] and arr2[i]
    # as pair in vector
    for i in range(N):
        v.append([arr1[i], arr2[i]])
 
    # Sort based on time spent
    # outside critical section (arr2[])
    v.sort(key = cmp_to_key(comp))
    geek,ans = 0,0
 
    # Loop to calculate total time
    for i in range(N):
        geek += v[i][0]
        ans = max(ans, geek + v[i][1])
    return ans
 
# Driver code
arr1 = [1, 4, 3]
arr2 = [2, 3, 1]
N = len(arr1)
 
# Function call
print(solution(arr1, arr2, N))
 
# This code is contributed by shinjanpatra

// C# program to implement the approach
using System;
using System.Collections.Generic;
 
public class GFG{
 
  // Comparator for sorting the vector of pair
  public class pair
  {
    public int first,second;
    public  pair(int s, int e)
    {
      this.first = s;
      this.second = e;
    }
 
 
  }
 
  // Function to find the total time taken
  static int solution(int []arr1, int []arr2, int N)
  {
    List<pair > v = new List<pair >();
 
    // Store all the arr1[i] and arr2[i]
    // as pair in vector
    for (int i = 0; i < N; i++)
      v.Add(new pair( arr1[i], arr2[i] ));
 
    // Sort based on time spent
    // outside critical section (arr2[])
    v.Sort((p1,p2)=>p2.second-p1.second);
    int geek = 0, ans = 0;
 
    // Loop to calculate total time
    for (int i = 0; i < N; i++) {
      geek += v[i].first;
      ans = Math.Max(ans, geek + v[i].second);
    }
    return ans;
  }
 
  // Driver code
  public static void Main(String[] args)
  {
    int []arr1 = { 1, 4, 3 };
    int []arr2 = { 2, 3, 1 };
    int N = arr1.Length;
 
    // Function call
    Console.Write(solution(arr1, arr2, N));
  }
}
 
// This code is contributed by Rajput-Ji

<script>
 
    // JavaScript program to implement the approach
 
    // Comparator for sorting the vector of pair
    const comp = (p1, p2) => {
        return p1[0] - p2[1];
    }
 
    // Function to find the total time taken
    const solution = (arr1, arr2, N) => {
        let v = [];
 
        // Store all the arr1[i] and arr2[i]
        // as pair in vector
        for (let i = 0; i < N; i++)
            v.push([arr1[i], arr2[i]]);
 
        // Sort based on time spent
        // outside critical section (arr2[])
        v.sort(comp);
        let geek = 0, ans = 0;
 
        // Loop to calculate total time
        for (let i = 0; i < N; i++) {
            geek += v[i][0];
            ans = Math.max(ans, geek + v[i][1]);
        }
        return ans;
    }
 
    // Driver code
 
    let arr1 = [1, 4, 3];
    let arr2 = [2, 3, 1];
    let N = arr1.length;
 
    // Function call
    document.write(solution(arr1, arr2, N));
 
    // This code is contributed by rakeshsahni
 
</script>

9

Complejidad temporal: O(N * logN)
Espacio auxiliar: O(N)