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 9Entrada: 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++
// 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
// 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
# 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#
// 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
Javascript
<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)
Publicación traducida automáticamente
Artículo escrito por dragonuncaged y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA