برنامه محاسبه حداقل سکوهای لازم برای ایستگاه قطار — راهنمای کاربردی

1// Program to find minimum number of platforms  
2// required on a railway station 
3#include<iostream> 
4#include<algorithm> 
5  
6using namespace std; 
7  
8// Returns minimum number of platforms reqquired 
9int findPlatform(int arr[], int dep[], int n) 
10{ 
11   // Sort arrival and departure arrays 
12   sort(arr, arr+n); 
13   sort(dep, dep+n); 
14  
15   // plat_needed indicates number of platforms 
16   // needed at a time 
17   int plat_needed = 1, result = 1; 
18   int i = 1, j = 0; 
19  
20   // Similar to merge in merge sort to process  
21   // all events in sorted order 
22   while (i < n && j < n) 
23   { 
24      // If next event in sorted order is arrival,  
25      // increment count of platforms needed 
26      if (arr[i] <= dep[j]) 
27      { 
28          plat_needed++; 
29          i++; 
30  
31          // Update result if needed  
32          if (plat_needed > result)  
33              result = plat_needed; 
34      } 
35  
36      // Else decrement count of platforms needed 
37      else
38      { 
39          plat_needed--; 
40          j++; 
41      } 
42   } 
43  
44   return result; 
45} 
46  
47// Driver program to test methods of graph class 
48int main() 
49{ 
50    int arr[] = {900, 940, 950, 1100, 1500, 1800}; 
51    int dep[] = {910, 1200, 1120, 1130, 1900, 2000}; 
52    int n = sizeof(arr)/sizeof(arr[0]); 
53    cout << "Minimum Number of Platforms Required = " 
54         << findPlatform(arr, dep, n); 
55    return 0; 
56}

1// Program to find minimum number of platforms  
2  
3import java.util.*; 
4  
5class GFG { 
6   
7// Returns minimum number of platforms reqquired 
8static int findPlatform(int arr[], int dep[], int n) 
9{ 
10   // Sort arrival and departure arrays 
11   Arrays.sort(arr); 
12   Arrays.sort(dep); 
13   
14   // plat_needed indicates number of platforms 
15   // needed at a time 
16   int plat_needed = 1, result = 1; 
17   int i = 1, j = 0; 
18   
19   // Similar to merge in merge sort to process  
20   // all events in sorted order 
21   while (i < n && j < n) 
22   { 
23      // If next event in sorted order is arrival,  
24      // increment count of platforms needed 
25      if (arr[i] <= dep[j]) 
26      { 
27          plat_needed++; 
28          i++; 
29   
30          // Update result if needed  
31          if (plat_needed > result)  
32              result = plat_needed; 
33      } 
34   
35      // Else decrement count of platforms needed 
36      else
37      { 
38          plat_needed--; 
39          j++; 
40      } 
41   } 
42   
43   return result; 
44} 
45   
46// Driver program to test methods of graph class 
47public static void main(String[] args) 
48{ 
49    int arr[] = {900, 940, 950, 1100, 1500, 1800}; 
50    int dep[] = {910, 1200, 1120, 1130, 1900, 2000}; 
51    int n = arr.length; 
52    System.out.println("Minimum Number of Platforms Required = "
53                        + findPlatform(arr, dep, n)); 
54} 
55}

1# Program to find minimum 
2# number of platforms  
3# required on a railway 
4# station 
5  
6# Returns minimum number 
7# of platforms reqquired 
8def findPlatform(arr,dep,n): 
9  
10    # Sort arrival and 
11    # departure arrays 
12    arr.sort() 
13    dep.sort() 
14   
15    # plat_needed indicates 
16    # number of platforms 
17    # needed at a time 
18    plat_needed = 1
19    result = 1
20    i = 1
21    j = 0
22   
23    # Similar to merge in 
24    # merge sort to process  
25    # all events in sorted order 
26    while (i < n and j < n): 
27     
28        # If next event in sorted 
29        # order is arrival,  
30        # increment count of 
31        # platforms needed 
32        if (arr[i] < dep[j]): 
33          
34            plat_needed+=1
35            i+=1
36   
37            # Update result if needed  
38            if (plat_needed > result):  
39                result = plat_needed 
40          
41   
42        # Else decrement count 
43        # of platforms needed 
44        else: 
45          
46            plat_needed-=1
47            j+=1
48          
49    return result 
50  
51# driver code 
52  
53arr = [900, 940, 950, 1100, 1500, 1800] 
54dep = [910, 1200, 1120, 1130, 1900, 2000] 
55n = len(arr) 
56  
57print("Minimum Number of Platforms Required = ", 
58        findPlatform(arr, dep, n)) 
59  
60# This code is contributed 
61# by Anant Agarwal.

1// C# program to find minimum number  
2// of platforms  
3using System; 
4  
5class GFG { 
6  
7    // Returns minimum number of platforms 
8    // reqquired 
9    static int findPlatform(int []arr,  
10                         int []dep, int n) 
11    { 
12          
13        // Sort arrival and departure arrays 
14        Array.Sort(arr); 
15        Array.Sort(dep); 
16          
17        // plat_needed indicates number of 
18        // platforms needed at a time 
19        int plat_needed = 1, result = 1; 
20        int i = 1, j = 0; 
21          
22        // Similar to merge in merge sort 
23        // to process all events in sorted 
24        // order 
25        while (i < n && j < n) 
26        { 
27              
28            // If next event in sorted order  
29            // is arrival, increment count 
30            // of platforms needed 
31            if (arr[i] <= dep[j]) 
32            { 
33                plat_needed++; 
34                i++; 
35          
36                // Update result if needed  
37                if (plat_needed > result)  
38                    result = plat_needed; 
39            } 
40          
41            // Else decrement count of  
42            // platforms needed 
43            else
44            { 
45                plat_needed--; 
46                j++; 
47            } 
48        } 
49          
50        return result; 
51    } 
52      
53    // Driver program to test methods of 
54    // graph class 
55    public static void Main() 
56    { 
57        int []arr = {900, 940, 950, 1100,  
58                                 1500, 1800}; 
59        int []dep = {910, 1200, 1120, 1130,  
60                                 1900, 2000}; 
61        int n = arr.Length; 
62        Console.Write("Minimum Number of "
63                  + " Platforms Required = "
64                + findPlatform(arr, dep, n)); 
65    } 
66} 
67  
68// This code os contributed by nitin mittal. 

1<?php 
2// PHP Program to find minimum number  
3// of platforms  required on a railway 
4// station 
5  
6// Returns minimum number of 
7// platforms reqquired 
8function findPlatform($arr, $dep, $n) 
9{ 
10      
11    // Sort arrival and  
12    // departure arrays 
13    sort($arr); 
14    sort($dep); 
15      
16    // plat_needed indicates 
17    // number of platforms 
18    // needed at a time 
19    $plat_needed = 1;  
20    $result = 1; 
21    $i = 1; 
22    $j = 0; 
23      
24    // Similar to merge in 
25    // merge sort to process  
26    // all events in sorted order 
27    while ($i < $n and $j < $n) 
28    { 
29          
30        // If next event in sorted  
31        // order is arrival, increment 
32        // count of platforms needed 
33        if ($arr[$i] <= $dep[$j]) 
34        { 
35            $plat_needed++; 
36            $i++; 
37      
38            // Update result if needed  
39            if ($plat_needed > $result)  
40                $result = $plat_needed; 
41        } 
42      
43        // Else decrement count  
44        // of platforms needed 
45        else
46        { 
47            $plat_needed--; 
48            $j++; 
49        } 
50    } 
51      
52    return $result; 
53} 
54  
55    // Driver Code 
56    $arr = array(900, 940, 950, 1100, 1500, 1800); 
57    $dep = array(910, 1200, 1120, 1130, 1900, 2000); 
58    $n = count($arr); 
59    echo "Minimum Number of Platforms Required = "
60                   , findPlatform($arr, $dep, $n); 
61  
62// This code os contributed by anuj_67. 
63?>