[Google] Minimum Number of Platforms Required for Trains

Problem: Given arrival and departure times of all trains that reach a railway station, the task is to find the minimum number of platforms required for the railway station so that no train waits. 

Example:

Input
arr = [10, 25, 50]
dep = [40, 55, 60]
Output
2

Approach: We can simply sort both the arrival and departure arrays. Once sorted we can follow the below steps:

• maxPlatforms = 0
• currPlatforms = 0
• arrIndex = 0
• depIndex = 0
• WHILE arrIndex < n AND depIndex < n
• IF arr[arrIndex] <= dep[depIndex]
• currPlatforms = currPlatforms + 1
• arrIndex = arrIndex + 1
• ELSE
• currPlatforms = currPlatforms - 1
• depIndex = depIndex + 1
• maxPlatforms = MAX (maxPlatforms,  currPlatforms)
• RETURN maxPlatforms

That's all!

Implementation in C#:

        public static int NumPlatformRequired(int[] arr, int[] dep)

        {

            if (arr?.Length == 0 || dep?.Length == 0)

            {

                return 0;

            }

            Array.Sort(arr);

            Array.Sort(dep);

            int maxPlatforms = 0, currPlatforms = 0, arrIndex = 0, depIndex = 0;

            while(arrIndex < arr.Length && depIndex < arr.Length) 

            {

                if (arr[arrIndex] <= dep[depIndex])

                {

                    ++currPlatforms;

                    ++arrIndex;

                }

                else

                {

                    --currPlatforms;

                    ++depIndex;

                }

                maxPlatforms = Math.Max(maxPlatforms, currPlatforms);

            }

            return maxPlatforms;

        }

Complexity: O(nlogn)