Greedy Algo

  1. Minimum Number of Platforms Required for a Railway/Bus Station.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.
    We are given two arrays which represent arrival and departure times of trains that stop  GFS.
    Also: We keep track of the arrival and departure of the train at any given point of time and keep a counter to count the maximum number of platform required. So if a train arrives we increase the country and when it departs we decrement the counter. For this to work perfectly all the arrival and departure time should be sorted. At the end we count the maximum value of the counter.
    Arrival and departure times are given in two array. We just need to sort the arrival and departure time. Merging them is not required. We can just navigate through both array simultaneously with same logic as we would have used for merging them.
    Time Complexity: O(nLogn)
    Similar: This is very similar to the problem of hotel booking. There instead of trains we have guests and room.

  2. Greedy Algorithm to find Minimum number of Coins Given a value V, if we want to make change for V Rs, and we have infinite supply of each of the denominations in Indian currency, i.e., we have infinite supply of { 1, 2, 5, 10, 20, 50, 100, 500, 1000} valued coins/notes, what is the minimum number of coins and/or notes needed to make the change?  GFG

    1) Initialize result as empty.
    2) find the largest denomination that is 
       smaller than V.
    3) Add found denomination to result. Subtract 
       value of found denomination from V.
    4) If V becomes 0, then print result.  
       Else repeat steps 2 and 3 for new value of V
  3. Find the point where maximum intervals overlap Consider a big party where a log register for guest’s entry and exit times is maintained. Find the time at which there are maximum guests in the party. Note that entries in register are not in any order. GFG
  4. Find memory conflicts among multiple threads GFG

Leave a Reply

Please log in using one of these methods to post your comment: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s