Greedy Programming

1. Fractional knapsack - There are n items. Each item has a weigh w(i) and value v(i). The total weight needed is W.

   • Calculate v(i)/w(i) for all. This gives value per unit weight for all. Now, sort the value per unit weight. Now, start with greatest value per unit weight item and add it. Then, second largest. Continue, this till W is achieved.

2. Single machine scheduling

   • There is a single machine. There are n works each of which have a starting time and a finish time. We have to find the maximum number of tasks that can be scheduled on that machine.
   • Sort by finish times of the works. Choose the work which finishes first. Then, choose the next work such that its start time isn't less than the finish time of the first work. And go on doing this...

3. Task scheduling problem

   • There are n tasks. Each has a start time and an end time. All tasks are to be scheduled. Find the smallest number of machines needed.
   • https://www.geeksforgeeks.org/minimum-number-platforms-required-railwaybus-station/

4. Huffman Encoding

   • You have to assign codes (prefix codes) to characters based on their frequency so that the overall cost of transmission is lowest.
   • https://www.geeksforgeeks.org/huffman-coding-greedy-algo-3/