Greedy Technique Problems

Greedy problems are a class of algorithmic problems where the solution is built incrementally, selecting the most optimal choice at each step with the hope that these local optimum choices will lead to a globally optimal solution.

Identification

1. Choice Property: At every step, you can make a decision that looks best at the moment and then solve the subproblem arising after the decision.

2. Optimal Substructure: A problem exhibits optimal substructure if an optimal solution to the problem contains an optimal solution to its subproblems.

N meetings on one room

To maximise the number of meetings we need to accommodate we will first take meetings that end quicky and hence we sort by end time.

Then we go on checking for Non-overlapping intervals

Minimum Platforms Required so no train is kept waiting

We need to calculate the maximum number of consecutive arrivals at any given instance - we would need at least those many platforms

Job Sequencing Problem🌟

Its implicit in the problem that the more number of jobs you can accommodate the more profit you can get apart from already picking high profit tasks first

Fractional Knapsack Problem

The idea is to take the items which have the most value -by weight

Activity Selection/Maximum Disjoint Intervals

The problem involves choosing various intervals such that maximum non-overlapping intervals can be chosen

The solution here is to SORT the intervals by END TIME, ensuring we have maximum remaining space

Then choose non-overlapping intervals among the above sorted intervals

Minimum Number of Chairs Needed

Non-overlapping intervals **

removing minimum ? === keeping maximum === sorting by ending time

1. Sort the Intervals: First, we need to sort the intervals based on their ending times. This helps us ensure that we always have the option to include the interval that ends the earliest, which maximizes the remaining space for subsequent intervals. As we want to remove minimal intervals. For example see input [[1,100],[11,22],[1,11],[2,12]]

2. Iterate Through the Intervals: After sorting, we iterate through the intervals while keeping track of the end of the last added interval to our non-overlapping set. If the current interval starts before the end of the last added interval, it overlaps, and we need to remove it. Otherwise, we include it in our set.

3. Count Removals: Each time we encounter an overlapping interval, we increment our removal counter. At the end of the iteration, the counter will hold the minimum number of intervals we need to remove to make the rest non-overlapping.

Merge Overlapping Intervals

It makes sense to sort above Intervals by start time, as in this way the subsequent interval has the highest chance of overlapping

Count Days Without Meetings

We have to return the count of days when the employee is available for work but no meetings are scheduled, instead of counting available, we will count un-available (reverse strategy) and then subtract from total .

Un-sorted intervals will definitely cause issue, it would also help if overlapping intervals are accounted for so we decide to merge intervals, for that we will need to sort intervals by start time