Greedy – DSA Notes

Greedy picks a local optimum that leads to a global optimum for certain classes of problems. Below are classic greedy patterns with crisp explanations, commented code, and quick takeaways.

---

📌 Summary Table

Problem	Greedy Key	Time	Space
N Meetings in a Room	Sort by earliest finishing time	O(n log n)	O(n)
Minimum Platforms	Two-pointer sweep on arrivals/departures	O(n log n)	O(1)
Job Sequencing (Deadlines & Profit)	Sort by profit, place in latest free slot ≤ deadline	O(n log n + n·D)	O(D)
Fractional Knapsack	Sort by value/weight ratio, take greedily	O(n log n)	O(1)

---

N Meetings in a Room

Problem. Given start and end times of n meetings, schedule the maximum number of non-overlapping meetings in one room.

Idea.

• Build (start, end) pairs.
• Sort by end time.
• Pick a meeting if its start time is strictly greater than the last selected end.

Complexity. O(n log n) time for sorting, O(n) space for pairs.

class Solution {
    public static int maxMeetings(int[] start, int[] end, int n) {
        // Build (start, end) pairs
        int[][] a = new int[n][2];
        for (int i = 0; i < n; i++) { a[i][0] = start[i]; a[i][1] = end[i]; }

        // Sort by earliest finishing time
        Arrays.sort(a, (x, y) -> Integer.compare(x[1], y[1]));

        int count = 0;
        int lastEnd = -1; // tracks end time of last selected meeting

        for (int i = 0; i < n; i++) {
            // Select if current start is strictly after last end
            if (a[i][0] > lastEnd) {
                count++;
                lastEnd = a[i][1];
            }
        }
        return count;
    }
}

Key Takeaway. Activity selection: sort by end time and pick greedily.

---

Minimum Platforms

Problem. Given arrival and departure times of trains, find the minimum number of platforms required so no train waits.

Idea.

• Sort arrivals and departures separately.

• Sweep with two pointers:

  • If arr[i] <= dep[j], a train arrives → need one more platform.
  • Else, a train departs → free one platform.

• Track the maximum concurrent platforms needed.

Complexity. O(n log n) time for sorting, O(1) extra space.

class Solution {
    static int findPlatform(int arr[], int dep[], int n) {
        Arrays.sort(arr);
        Arrays.sort(dep);

        int i = 0, j = 0;      // pointers for arrivals and departures
        int plat = 0, ans = 0; // current platforms needed, max platforms

        while (i < n && j < n) {
            if (arr[i] <= dep[j]) { // a train arrives before next departure
                plat++;             // need a platform
                i++;
                ans = Math.max(ans, plat); // update max
            } else {                 // next event is a departure
                plat--;             // free a platform
                j++;
            }
        }
        return ans;
    }
}

Key Takeaway. Two-pointer timeline sweep on sorted arrivals/departures.

---

Job Sequencing (Deadlines & Profit)

Problem. Given n jobs with deadline and profit. Each job takes one unit time and only one job can be done at a time. Maximize total profit by scheduling jobs before or on their deadlines.

Idea.

• Sort jobs by profit descending.
• Use a slot array for time 1..maxDeadline.
• For each job, greedily place it in the latest free slot ≤ deadline.

Complexity.

• Sorting: O(n log n)
• Placement: O(n · maxDeadline) (can be optimized to O(n α(n)) with DSU)

class Solution {
    int[] JobScheduling(Job arr[], int n) {
        // Sort jobs by profit (highest first)
        Arrays.sort(arr, (a, b) -> b.profit - a.profit);

        // Find the maximum deadline to size the slot array
        int maxD = 0;
        for (Job j : arr) maxD = Math.max(maxD, j.deadline);

        // slot[d] = index of job occupying time d, or -1 if free
        int[] slot = new int[maxD + 1];
        Arrays.fill(slot, -1);

        int jobs = 0, profit = 0;

        // Try to place each job in the latest possible free slot
        for (int i = 0; i < n; i++) {
            for (int d = arr[i].deadline; d > 0; d--) {
                if (slot[d] == -1) {        // slot free
                    slot[d] = i;            // schedule job i at time d
                    jobs++;
                    profit += arr[i].profit;
                    break;                  // move to next job
                }
            }
        }
        return new int[]{jobs, profit};
    }
}

Key Takeaway. Sort by profit, then place each job in the latest free slot ≤ deadline.

---

Fractional Knapsack

Problem. Given capacity W and items with value and weight, maximize total value by taking whole or fractional parts of items.

Idea.

• Sort items by value/weight ratio descending.
• Take as much as possible from each item; take fraction of the last one if needed.

Complexity. O(n log n) time for sorting, O(1) extra space.

class Solution {
    double fractionalKnapsack(int W, Item[] arr, int n) {
        // Sort by value/weight ratio (descending)
        Arrays.sort(arr, (a, b) -> Double.compare(
            (double) b.value / b.weight, (double) a.value / a.weight
        ));

        int curW = 0;
        double val = 0.0;

        for (Item it : arr) {
            if (curW + it.weight <= W) {
                // Take whole item
                curW += it.weight;
                val += it.value;
            } else {
                // Take fractional part to fill capacity
                int remain = W - curW;
                val += ((double) it.value / it.weight) * remain;
                break; // knapsack is full
            }
        }
        return val;
    }
}

Key Takeaway. Greedy by highest value density (value/weight).

---