我们得到了n个进程，它们的完成时间是以数组的形式给出的。我们需要找到给定进程p结束的时刻，如果调度进程是 循环赛 时间片是1秒。 注意：数组索引以0开头。 例如：
null
Input : arr[] = {3, 2, 4, 2}, p = 1Output : Completion time = 6Explanation : Snap of process for every second is as:Time | Process Array0 | {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 = 2Output :Completion time = 3Explanation : Snap of process for every second is as:Time | Process Array0 | {2, 4, 1, 3}1 | {1, 4, 1, 3}2 | {1, 3, 1, 3}3 | {1, 3, 0, 3}
蛮力： 解决这个问题的基本方法是使用时间片1的循环算法。但这种方法的时间复杂度将是O（∑Ai），即所有进程时间的总和，这相当高。 有效方法： 这个想法基于以下观察。 1） CPU时间小于arr[p]的所有进程都将在arr[p]之前完成。我们只需要增加这些过程的时间。 2） 我们还需要增加arr的时间[p]。 3） 对于CPU时间超过arr[p]的每个进程x，会出现两种情况： …..（i） 如果x在arr[p]的左边（计划在arr[p]之前），那么这个过程在p完成之前需要CPU的arr[p]时间。 …..（ii）如果x在arr[p]的右边（计划在arr[p]之后），那么这个过程在p完成之前需要arr[p]-1倍的CPU时间。 算法：
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 ptime_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> |
输出：
Completion time = 9
时间复杂性： O（n）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
