Se nos dan n procesos con sus tiempos de finalización en forma de array. Necesitamos encontrar el instante de tiempo cuando finaliza un proceso p dado si el proceso de programación es por turnos y el intervalo de tiempo es de 1 segundo.
nota: el índice de array comienza con 0.
Ejemplos:
Input : arr[] = {3, 2, 4, 2}, p = 1
Output : Completion time = 6
Explanation : Snap of process for every second is as:
Time | Process Array
0 | {3, 2, 4, 2}
1 | {2, 2, 4, 2}
2 | {2, 1, 4, 2}
3 | {2, 1, 3, 2}
4 | {2, 1, 3, 1}
5 | {1, 1, 3, 1}
6 | {1, 0, 3, 1}
Input : arr[] = {2, 4, 1, 3}, p = 2
Output :Completion time = 3
Explanation : Snap of process for every second is as:
Time | Process Array
0 | {2, 4, 1, 3}
1 | {1, 4, 1, 3}
2 | {1, 3, 1, 3}
3 | {1, 3, 0, 3}
Fuerza bruta: el enfoque básico para resolver este problema es aplicar el algoritmo de todos contra todos con el intervalo de tiempo 1. Pero la complejidad temporal de ese enfoque será O(ΣAi), es decir, la suma del tiempo de todos los procesos, que es bastante alta.
Enfoque eficiente: la idea se basa en las siguientes observaciones.
1) Todos los procesos con tiempo de CPU menor que arr[p] se completarían antes que arr[p]. Simplemente necesitamos agregar tiempo a estos procesos.
2) También necesitamos agregar la hora de arr[p].
3) Para cada proceso x con tiempo de CPU mayor que arr[p], surgen dos casos:
…..(i) Si x está a la izquierda de arr[p] (programado antes de arr[p]), entonces este proceso toma arr [p] tiempo de CPU antes de que finalice p.
…..(ii) Si x está a la derecha de arr[p] (programado después de arr[p]), entonces este proceso requiere arr[p]-1 tiempo de CPU antes de que finalice p.
Algoritmo:
time_req = 0;
// Add time for process on left of p
// (Scheduled before p in a round of
// 1 unit time slice)
for (int i=0; i<p; i++)
{
if (arr[i] < arr[p])
time_req += arr[i];
else
time_req += arr[p];
}
// step 2 : Add time of process p
time_req += arr[p];
// Add time for process on right
// of p (Scheduled after p in
// a round of 1 unit time slice)
for (int i=p+1; i<n; i++)
{
if (arr[i] < arr[p])
time_req += arr[i];
else
time_req += arr[p]-1;
}
C++
// Program to find end time of a process
// p in round robin scheduling with unit
// time slice.
#include <bits/stdc++.h>
using namespace std;
// Returns completion time of p.
int completionTime(int arr[], int n, int p) {
// Initialize result
int time_req = 0;
// Step 1 : Add time of processes on left
// of p (Scheduled before p)
for (int i = 0; i < p; i++) {
if (arr[i] < arr[p])
time_req += arr[i];
else
time_req += arr[p];
}
// Step 2 : Add time of p
time_req += arr[p];
// Step 3 : Add time of processes on right
// of p (Scheduled after p)
for (int i = p + 1; i < n; i++) {
if (arr[i] < arr[p])
time_req += arr[i];
else
time_req += arr[p] - 1;
}
return time_req;
}
// driver program
int main() {
int arr[] = {3, 5, 2, 7, 6, 1};
int n = sizeof(arr) / sizeof(arr[0]);
int p = 2;
cout << "Completion time = "
<< completionTime(arr, n, p);
return 0;
}
Java
// Program to find end time of a process
// p in round robin scheduling with unit
// time slice.
class GFG
{
// Returns completion time of p.
static int completionTime(int arr[], int n, int p) {
// Initialize result
int time_req = 0;
// Step 1 : Add time of processes on left
// of p (Scheduled before p)
for (int i = 0; i < p; i++) {
if (arr[i] < arr[p])
time_req += arr[i];
else
time_req += arr[p];
}
// Step 2 : Add time of p
time_req += arr[p];
// Step 3 : Add time of processes on right
// of p (Scheduled after p)
for (int i = p + 1; i < n; i++) {
if (arr[i] < arr[p])
time_req += arr[i];
else
time_req += arr[p] - 1;
}
return time_req;
}
// Driver code
public static void main (String[] args)
{
int arr[] = {3, 5, 2, 7, 6, 1};
int n =arr.length;;
int p = 2;
System.out.print("Completion time = "+
completionTime(arr, n, p));
}
}
// This code is contributed by Anant Agarwal.
Python
# Program to find end time of a process
# p in round robin scheduling with unit
# time slice.
# Returns completion time of p.
def completionTime(arr, n, p) :
# Initialize result
time_req = 0
# Step 1 : Add time of processes on
# left of p (Scheduled before p)
for i in range(0, p):
if (arr[i] < arr[p]):
time_req += arr[i]
else:
time_req += arr[p]
# Step 2 : Add time of p
time_req += arr[p]
# Step 3 : Add time of processes on
# right of p (Scheduled after p)
for i in range(p + 1, n):
if (arr[i] < arr[p]):
time_req += arr[i]
else:
time_req += arr[p] - 1
return time_req
# driver program
arr = [3, 5, 2, 7, 6, 1]
n = len(arr)
p = 2
print("Completion time =",
completionTime(arr, n, p))
# This code is contributed by
# Smitha Dinesh Semwal
C#
// C# program to find end time of a process
// p in round robin scheduling with unit
// time slice.
using System;
class GFG {
// Returns completion time of p.
static int completionTime(int []arr,
int n, int p)
{
// Initialize result
int time_req = 0;
// Step 1 : Add time of processes
// on left of p (Scheduled before p)
for (int i = 0; i < p; i++) {
if (arr[i] < arr[p])
time_req += arr[i];
else
time_req += arr[p];
}
// Step 2 : Add time of p
time_req += arr[p];
// Step 3 : Add time of processes on
// right of p (Scheduled after p)
for (int i = p + 1; i < n; i++) {
if (arr[i] < arr[p])
time_req += arr[i];
else
time_req += arr[p] - 1;
}
return time_req;
}
// Driver code
public static void Main ()
{
int []arr = {3, 5, 2, 7, 6, 1};
int n =arr.Length;;
int p = 2;
Console.WriteLine("Completion time = "+
completionTime(arr, n, p));
}
}
// This code is contributed by vt_m.
PHP
<?php
// Program to find end time
// of a process p in round
// robin scheduling with
// unit time slice.
// Returns completion time of p.
function completionTime($arr, $n, $p)
{
// Initialize result
$time_req = 0;
// Step 1 : Add time of processes on
// left of p (Scheduled before p)
for ($i = 0; $i < $p; $i++)
{
if ($arr[$i] < $arr[$p])
$time_req += $arr[$i];
else
$time_req += $arr[$p];
}
// Step 2 : Add time of p
$time_req += $arr[$p];
// Step 3 : Add time of processes on
// right of p (Scheduled after p)
for ($i = $p + 1; $i < $n; $i++)
{
if ($arr[$i] < $arr[$p])
$time_req += $arr[$i];
else
$time_req += $arr[$p] - 1;
}
return $time_req;
}
// Driver Code
$arr = array(3, 5, 2, 7, 6, 1);
$n = count($arr);
$p = 2;
echo"Completion time = " ,
completionTime($arr, $n, $p);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Program to find end time of a process
// p in round robin scheduling with unit
// time slice.
// Returns completion time of p.
function completionTime(arr, n, p) {
// Initialize result
var time_req = 0;
// Step 1 : Add time of processes on left
// of p (Scheduled before p)
for (var i = 0; i < p; i++) {
if (arr[i] < arr[p])
time_req += arr[i];
else
time_req += arr[p];
}
// Step 2 : Add time of p
time_req += arr[p];
// Step 3 : Add time of processes on right
// of p (Scheduled after p)
for (var i = p + 1; i < n; i++) {
if (arr[i] < arr[p])
time_req += arr[i];
else
time_req += arr[p] - 1;
}
return time_req;
}
// driver program
var arr = [3, 5, 2, 7, 6, 1];
var n = arr.length;
var p = 2;
document.write( "Completion time = "
+ completionTime(arr, n, p));
// This code is contributed by noob2000.
</script>
Producción :
Completion time = 9
Complejidad de tiempo : O(n)
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA