Рубрики

Минимальное количество платформ, необходимых для железнодорожного / автобусного вокзала

С учетом времени прибытия и отправления всех поездов, которые достигают железнодорожной станции, задача состоит в том, чтобы найти минимальное количество платформ, необходимых для железнодорожной станции, чтобы поезд не ожидал.
Нам дают два массива, которые представляют время прибытия и отправления поездов, которые останавливаются

Примеры:

Input: arr[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}
dep[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}
Output: 3
There are at-most three trains at a time (time between 11:00 to 11:20)

Нам нужно найти максимальное количество поездов, которые есть на данной железнодорожной станции за один раз. Простое решение состоит в том, чтобы взять каждый интервал один за другим и найти количество интервалов, которые перекрывают его. Отслеживайте максимальное количество интервалов, которые перекрываются с интервалом. Наконец, верните максимальное значение. Сложность времени этого решения O (n 2 ).

Мы можем решить вышеупомянутую проблему за O (N Log N) времени . Идея состоит в том, чтобы рассмотреть все события в отсортированном порядке. Как только все события будут отсортированы, мы можем отслеживать количество поездов в любое время, отслеживая прибывшие, но не отправившиеся поезда.

Например рассмотрим приведенный выше пример.

    arr[]  = {9:00,  9:40, 9:50,  11:00, 15:00, 18:00}
    dep[]  = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}

All events sorted by time.
Total platforms at any time can be obtained by subtracting total 
departures from total arrivals by that time.
 Time     Event Type     Total Platforms Needed at this Time                               
 9:00       Arrival                  1
 9:10       Departure                0
 9:40       Arrival                  1
 9:50       Arrival                  2
 11:00      Arrival                  3 
 11:20      Departure                2
 11:30      Departure                1
 12:00      Departure                0
 15:00      Arrival                  1
 18:00      Arrival                  2 
 19:00      Departure                1
 20:00      Departure                0

Minimum Platforms needed on railway station = Maximum platforms 
                                              needed at any time 
                                           = 3  

Ниже приведена реализация вышеуказанного подхода. Обратите внимание, что реализация не создает единый отсортированный список всех событий, скорее, она индивидуально сортирует массивы arr [] и dep [], а затем использует процесс слияния сортировки слиянием, чтобы обрабатывать их вместе как один отсортированный массив.

Примечание. Этот подход предполагает, что поезда прибывают и отправляются в одну и ту же дату.

C ++

// Программа для поиска минимального количества платформ
// требуется на железнодорожной станции
#include<iostream>
#include<algorithm>

  

using namespace std;

  
// Возвращает минимальное количество требуемых платформ

int findPlatform(int arr[], int dep[], int n)

{

   // Сортировка массивов прибытия и отправления

   sort(arr, arr+n);

   sort(dep, dep+n);

  

   // plat_needed указывает количество платформ

   // необходимо за один раз

   int plat_needed = 1, result = 1;

   int i = 1, j = 0;

  

   // Аналогично слиянию в сортировке слиянием для обработки

   // все события в отсортированном порядке

   while (i < n && j < n)

   {

      // Если следующим событием в отсортированном порядке является прибытие,

      // увеличение количества нужных платформ

      if (arr[i] <= dep[j])

      {

          plat_needed++;

          i++;

  

          // Обновить результат, если необходимо

          if (plat_needed > result) 

              result = plat_needed;

      }

  

      // Остальное требуется уменьшить количество платформ

      else

      {

          plat_needed--;

          j++;

      }

   }

  

   return result;

}

  
// Программа драйвера для тестирования методов класса графа

int main()

{

    int arr[] = {900, 940, 950, 1100, 1500, 1800};

    int dep[] = {910, 1200, 1120, 1130, 1900, 2000};

    int n = sizeof(arr)/sizeof(arr[0]);

    cout << "Minimum Number of Platforms Required = " 

         << findPlatform(arr, dep, n);

    return 0;

}

Джава

// Программа для поиска минимального количества платформ

  

import java.util.*;

  

class GFG {

   
// Возвращает минимальное количество требуемых платформ

static int findPlatform(int arr[], int dep[], int n)

{

   // Сортировка массивов прибытия и отправления

   Arrays.sort(arr);

   Arrays.sort(dep);

   

   // plat_needed указывает количество платформ

   // необходимо за один раз

   int plat_needed = 1, result = 1;

   int i = 1, j = 0;

   

   // Аналогично слиянию в сортировке слиянием для обработки

   // все события в отсортированном порядке

   while (i < n && j < n)

   {

      // Если следующим событием в отсортированном порядке является прибытие,

      // увеличение количества нужных платформ

      if (arr[i] <= dep[j])

      {

          plat_needed++;

          i++;

   

          // Обновить результат, если необходимо

          if (plat_needed > result) 

              result = plat_needed;

      }

   

      // Остальное требуется уменьшить количество платформ

      else

      {

          plat_needed--;

          j++;

      }

   }

   

   return result;

}

   
// Программа драйвера для тестирования методов класса графа

public static void main(String[] args)

{

    int arr[] = {900, 940, 950, 1100, 1500, 1800};

    int dep[] = {910, 1200, 1120, 1130, 1900, 2000};

    int n = arr.length;

    System.out.println("Minimum Number of Platforms Required = "

                        + findPlatform(arr, dep, n));

}
}

python3

# Программа для поиска минимума
# количество платформ
# требуется на железной дороге
# станция

  
# Возвращает минимальное количество
Количество платформ требуется

def findPlatform(arr,dep,n):

  

    # Сортировка прибытия и

    # массивы отправления

    arr.sort()

    dep.sort()

   

    # plat_needed указывает

    # количество платформ

    # нужно за один раз

    plat_needed = 1

    result = 1

    i = 1

    j = 0

   

    # Аналогично слиянию в

    # объединить сортировку в процесс

    # все события в отсортированном порядке

    while (i < n and j < n):

     

        # Если следующее событие отсортировано

        # заказ - прибытие,

        число приращений

        количество платформ

        if (arr[i] < dep[j]):

          

            plat_needed+=1

            i+=1

   

            # Обновить результат при необходимости

            if (plat_needed > result): 

                result = plat_needed

          

   

        # Еще счетчик декрементов

        Количество платформ, необходимых

        else:

          

            plat_needed-=1

            j+=1

          

    return result

  
# код водителя

  

arr = [900, 940, 950, 1100, 1500, 1800]

dep = [910, 1200, 1120, 1130, 1900, 2000]

n = len(arr)

  

print("Minimum Number of Platforms Required = ",

        findPlatform(arr, dep, n))

  
# Этот код добавлен
# Анант Агарвал.

C #

// C # программа для поиска минимального числа
// платформ

using System;

  

class GFG {

  

    // Возвращает минимальное количество платформ

    // Требуется

    static int findPlatform(int []arr, 

                         int []dep, int n)

    {

          

        // Сортировка массивов прибытия и отправления

        Array.Sort(arr);

        Array.Sort(dep);

          

        // plat_needed указывает номер

        // Платформы, необходимые одновременно

        int plat_needed = 1, result = 1;

        int i = 1, j = 0;

          

        // Аналогично слиянию в сортировке слиянием

        // обрабатывать все события в отсортированном

        // заказ

        while (i < n && j < n)

        {

              

            // Если следующее событие в отсортированном порядке

            // это прибытие, счетчик приращений

            // платформ, необходимых

            if (arr[i] <= dep[j])

            {

                plat_needed++;

                i++;

          

                // Обновить результат, если необходимо

                if (plat_needed > result) 

                    result = plat_needed;

            }

          

            // Иначе счетчик декрементов

            // нужны платформы

            else

            {

                plat_needed--;

                j++;

            }

        }

          

        return result;

    }

      

    // Программа драйвера для тестирования методов

    // класс графика

    public static void Main()

    {

        int []arr = {900, 940, 950, 1100, 

                                 1500, 1800};

        int []dep = {910, 1200, 1120, 1130, 

                                 1900, 2000};

        int n = arr.Length;

        Console.Write("Minimum Number of "

                  + " Platforms Required = "

                + findPlatform(arr, dep, n));

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// PHP программа для поиска минимального числа
// платформ на железной дороге
// станция

  
// Возвращает минимальное количество
// Требуются платформы

function findPlatform($arr, $dep, $n)

{

      

    // Сортировка прибытия и

    // массивы отправления

    sort($arr);

    sort($dep);

      

    // plat_needed указывает

    // количество платформ

    // необходимо за один раз

    $plat_needed = 1; 

    $result = 1;

    $i = 1;

    $j = 0;

      

    // Аналогично слиянию в

    // объединить сортировку в процесс

    // все события в отсортированном порядке

    while ($i < $n and $j < $n)

    {

          

        // Если следующее событие отсортировано

        // заказ поступление, приращение

        // нужно количество платформ

        if ($arr[$i] <= $dep[$j])

        {

            $plat_needed++;

            $i++;

      

            // Обновить результат, если необходимо

            if ($plat_needed > $result

                $result = $plat_needed;

        }

      

        // Еще счетчик декрементов

        // платформ, необходимых

        else

        {

            $plat_needed--;

            $j++;

        }

    }

      

    return $result;

}

  

    // Код драйвера

    $arr = array(900, 940, 950, 1100, 1500, 1800);

    $dep = array(910, 1200, 1120, 1130, 1900, 2000);

    $n = count($arr);

    echo "Minimum Number of Platforms Required = "

                   , findPlatform($arr, $dep, $n);

  
// Этот код предоставлен anuj_67.
?>


Выход :

Minimum Number of Platforms Required = 3

Алгоритмическая парадигма : динамическое программирование

Сложность времени : O (N Log N), предполагая, что алгоритм сортировки O (N Log N) для сортировки arr [] и dep [].

Минимальное количество платформ, необходимых для железнодорожного / автобусного вокзала | Набор 2 (основанный на карте подход)

Эта статья предоставлена Шивам . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Минимальное количество платформ, необходимых для железнодорожного / автобусного вокзала

0.00 (0%) 0 votes