{"id":25131,"date":"2017-10-15T14:38:31","date_gmt":"2017-10-15T09:08:31","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25131"},"modified":"2017-10-15T14:38:31","modified_gmt":"2017-10-15T09:08:31","slug":"minimum-number-platforms-required-railwaybus-station","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/minimum-number-platforms-required-railwaybus-station\/","title":{"rendered":"Minimum Number of Platforms Required for a Railway\/Bus Station"},"content":{"rendered":"

Given arrival and departure times of all trains that reach a railway station, find the minimum number of platforms required for the railway station so that no train waits.<\/span>
\nWe are given two arrays which represent arrival and departure times of trains that stop<\/p>\n

Examples:<\/p>\n

Input:  arr[]  = {9:00,  9:40, 9:50,  11:00, 15:00, 18:00}\r\n        dep[]  = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}\r\nOutput: 3\r\nThere are at-most three trains at a time (time between 11:00 to 11:20)\r\n<\/pre>\n
\n
Recommended: Please try your approach on {IDE}<\/u><\/i><\/b> first, before moving on to the solution.<\/h4>\n<\/div>\n
We need to find the maximum number of trains that are there on the given railway station at a time. A Simple Solution<\/strong> is to take every interval one by one and find the number of intervals that overlap with it. Keep track of maximum number of intervals that overlap with an interval. Finally return the maximum value. Time Complexity of this solution is O(n2<\/sup>).<\/p>\n
We can solve the above problem in O(nLogn) time<\/strong>. The idea is to consider all evens in sorted order. Once we have all events in sorted order, we can trace the number of trains at any time keeping track of trains that have arrived, but not departed.<\/p>\n[ad type=\u201dbanner\u201d]\n
For example consider the above example.<\/p>\n
    arr[]  = {9:00,  9:40, 9:50,  11:00, 15:00, 18:00}\r\n    dep[]  = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}\r\n\r\nAll events sorted by time.<\/strong>\r\nTotal platforms at any time can be obtained by subtracting total \r\ndepartures from total arrivals by that time.\r\n Time     Event Type     Total Platforms Needed at this Time                               \r\n 9:00       Arrival                  1\r\n 9:10       Departure                0\r\n 9:40       Arrival                  1\r\n 9:50       Arrival                  2\r\n 11:00      Arrival                  3 \r\n 11:20      Departure                2\r\n 11:30      Departure                1\r\n 12:00      Departure                0\r\n 15:00      Arrival                  1\r\n 18:00      Arrival                  2 \r\n 19:00      Departure                1\r\n 20:00      Departure                0\r\n\r\nMinimum Platforms needed on railway station = Maximum platforms \r\n                                              needed at any time \r\n                                           = 3  \r\n<\/pre>\n
Following is C++ implementation of above approach. Note that the implementation doesn\u2019t create a single sorted list of all events, rather it individually sorts arr[] and dep[] arrays, and then uses merge process of merge sort to process them together as a single sorted array.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20Program%20to%20find%20minimum%20number%20of%20platforms%20required%20on%20a%20railway%20station%0A%23include%3Ciostream%3E%0A%23include%3Calgorithm%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20Returns%20minimum%20number%20of%20platforms%20reqquired%0Aint%20findPlatform(int%20arr%5B%5D%2C%20int%20dep%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%2F%2F%20Sort%20arrival%20and%20departure%20arrays%0A%20%20%20sort(arr%2C%20arr%2Bn)%3B%0A%20%20%20sort(dep%2C%20dep%2Bn)%3B%0A%20%0A%20%20%20%2F%2F%20plat_needed%20indicates%20number%20of%20platforms%20needed%20at%20a%20time%0A%20%20%20int%20plat_needed%20%3D%201%2C%20result%20%3D%201%3B%0A%20%20%20int%20i%20%3D%201%2C%20j%20%3D%200%3B%0A%20%0A%20%20%20%2F%2F%20Similar%20to%20merge%20in%20merge%20sort%20to%20process%20all%20events%20in%20sorted%20order%0A%20%20%20while%20(i%20%3C%20n%20%26%26%20j%20%3C%20n)%0A%20%20%20%7B%0A%20%20%20%20%20%20%2F%2F%20If%20next%20event%20in%20sorted%20order%20is%20arrival%2C%20increment%20count%20of%0A%20%20%20%20%20%20%2F%2F%20platforms%20needed%0A%20%20%20%20%20%20if%20(arr%5Bi%5D%20%3C%20dep%5Bj%5D)%0A%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20plat_needed%2B%2B%3B%0A%20%20%20%20%20%20%20%20%20%20i%2B%2B%3B%0A%20%20%20%20%20%20%20%20%20%20if%20(plat_needed%20%3E%20result)%20%20%2F%2F%20Update%20result%20if%20needed%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20result%20%3D%20plat_needed%3B%0A%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20else%20%2F%2F%20Else%20decrement%20count%20of%20platforms%20needed%0A%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20plat_needed\u2013%3B%0A%20%20%20%20%20%20%20%20%20%20j%2B%2B%3B%0A%20%20%20%20%20%20%7D%0A%20%20%20%7D%0A%20%0A%20%20%20return%20result%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20methods%20of%20graph%20class%0Aint%20main()%0A%7B%0A%20%20%20%20int%20arr%5B%5D%20%3D%20%7B900%2C%20940%2C%20950%2C%201100%2C%201500%2C%201800%7D%3B%0A%20%20%20%20int%20dep%5B%5D%20%3D%20%7B910%2C%201200%2C%201120%2C%201130%2C%201900%2C%202000%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%20%20%20cout%20%3C%3C%20%22Minimum%20Number%20of%20Platforms%20Required%20%3D%20%22%0A%20%20%20%20%20%20%20%20%20%3C%3C%20findPlatform(arr%2C%20dep%2C%20n)%3B%0A%20%20%20%20return%200%3B%0A%7D%0A\u201d message=\u201dc\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Output:<\/strong><\/p>\n
Minimum Number of Platforms Required = 3<\/pre>\n
Algorithmic Paradigm: Dynamic Programming<\/p>\n
<\/div>\n
Time Complexity: O(nLogn), assuming that a O(nLogn) sorting algorithm for sorting arr[] and dep[].<\/p>\n
Minimum Number of Platforms Required = 3<\/pre>\n
Algorithmic Paradigm: Dynamic Programming<\/p>\n
<\/div>\n
Time Complexity: O(nLogn), assuming that a O(nLogn) sorting algorithm for sorting arr[] and dep[].<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
Minimum No of Platforms Required for a Railway\/Bus Station – Greedy algorithm – Given arrival and departure times of all trains that reach a railway station , to find the minimum number of platforms required for the railway station so that no train waits.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,73904,70144],"tags":[71662,71657,71623,71616,71637,71612,71614,71641,71628,71624,71617,71640,71629,71636,71644,71620,71634,71619,71664,71621,71663,71646,71635,71658,71639,71661,71660,71633,71655,71618,71647,71659,71648,71651,56573,71609,71653,71649,71645,71613,71652,71608,71643,71610,71615,71630,71631,71632,71626,71650,71665,71656,71654,71642,71638,71627,71611,71625,71622],"class_list":["post-25131","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-backtracking","category-greedy-algorithm","tag-arrival-train","tag-find-my-train","tag-find-train","tag-find-your-train","tag-indian-enquiry","tag-indian-railway-location","tag-indian-railway-train","tag-indian-railway-train-enquiry","tag-indian-train-enquary","tag-live-railway-station","tag-live-station-train","tag-live-train-enquiry","tag-live-train-information","tag-live-train-running-station","tag-live-train-station","tag-live-train-times","tag-live-train-tracker","tag-liverail","tag-locate-my-train","tag-locate-train","tag-locate-your-train","tag-online-train-enquiry","tag-online-train-tracking","tag-platform-enquiry","tag-platform-locator","tag-platform-number","tag-platform-status","tag-railway-inquiry-number","tag-railway-running-information","tag-railway-train-enquiry","tag-running-train-enquiry","tag-running-train-info","tag-running-train-information","tag-track-the-train","tag-train-apps","tag-train-apps-free","tag-train-arrival-status","tag-train-arrival-times","tag-train-between-stations-live","tag-train-check","tag-train-departure-time","tag-train-enquiry","tag-train-enquiry-number","tag-train-information-apps","tag-train-live-enquiry","tag-train-live-running","tag-train-live-station","tag-train-live-tracking","tag-train-number-enquiry","tag-train-platform","tag-train-platform-enquiry","tag-train-running-enquiry","tag-train-running-info","tag-train-running-live","tag-train-running-time","tag-train-schedule-live","tag-train-time-app","tag-train-time-enquiry","tag-train-times-live"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25131","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25131"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25131\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25131"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25131"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25131"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}