This content originally appeared on DEV Community and was authored by DevCorner2
Greedy strategy = make the best local choice at each step with the expectation of achieving the global optimum.
Not all problems work with greedy, but when they do → super efficient.
🔹 Problem 1: Activity / Interval Scheduling
📌 Maximize number of non-overlapping meetings.
import java.util.*;
public class ActivitySelection {
public static int maxMeetings(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
int count = 0, end = -1;
for (int[] interval : intervals) {
if (interval[0] >= end) {
count++;
end = interval[1];
}
}
return count;
}
public static void main(String[] args) {
int[][] intervals = {{1,2},{3,4},{0,6},{5,7},{8,9},{5,9}};
System.out.println(maxMeetings(intervals)); // 4
}
}
✅ Time Complexity: O(N log N)
🔹 Problem 2: Minimum Number of Platforms
📌 Trains arrival/departure schedule → min platforms required.
import java.util.*;
public class MinPlatforms {
public static int findPlatforms(int[] arr, int[] dep) {
Arrays.sort(arr);
Arrays.sort(dep);
int i = 0, j = 0, platforms = 0, maxPlatforms = 0;
while (i < arr.length && j < dep.length) {
if (arr[i] <= dep[j]) {
platforms++;
maxPlatforms = Math.max(maxPlatforms, platforms);
i++;
} else {
platforms--;
j++;
}
}
return maxPlatforms;
}
public static void main(String[] args) {
int[] arr = {900, 940, 950, 1100, 1500, 1800};
int[] dep = {910, 1200, 1120, 1130, 1900, 2000};
System.out.println(findPlatforms(arr, dep)); // 3
}
}
✅ Time Complexity: O(N log N)
🔹 Problem 3: Jump Game
📌 Can you reach last index with given jump lengths?
public class JumpGame {
public static boolean canJump(int[] nums) {
int reachable = 0;
for (int i = 0; i < nums.length; i++) {
if (i > reachable) return false;
reachable = Math.max(reachable, i + nums[i]);
}
return true;
}
public static void main(String[] args) {
System.out.println(canJump(new int[]{2,3,1,1,4})); // true
System.out.println(canJump(new int[]{3,2,1,0,4})); // false
}
}
✅ Time Complexity: O(N)
🔹 Problem 4: Gas Station (Circular Tour)
📌 Given gas[i] and cost[i], find starting station index to complete the circuit.
public class GasStation {
public static int canCompleteCircuit(int[] gas, int[] cost) {
int total = 0, tank = 0, start = 0;
for (int i = 0; i < gas.length; i++) {
total += gas[i] - cost[i];
tank += gas[i] - cost[i];
if (tank < 0) {
start = i + 1;
tank = 0;
}
}
return total >= 0 ? start : -1;
}
public static void main(String[] args) {
int[] gas = {1,2,3,4,5};
int[] cost = {3,4,5,1,2};
System.out.println(canCompleteCircuit(gas, cost)); // 3
}
}
✅ Time Complexity: O(N)
🔹 Problem 5: Fractional Knapsack
📌 Maximize profit with weight capacity, can take fractions.
import java.util.*;
class Item {
int weight, value;
Item(int v, int w) { value = v; weight = w; }
}
public class FractionalKnapsack {
public static double getMaxValue(Item[] items, int capacity) {
Arrays.sort(items, (a, b) -> Double.compare((double)b.value/b.weight, (double)a.value/a.weight));
double totalValue = 0.0;
for (Item item : items) {
if (capacity >= item.weight) {
capacity -= item.weight;
totalValue += item.value;
} else {
totalValue += (double)item.value * capacity / item.weight;
break;
}
}
return totalValue;
}
public static void main(String[] args) {
Item[] items = {new Item(60, 10), new Item(100, 20), new Item(120, 30)};
System.out.println(getMaxValue(items, 50)); // 240.0
}
}
✅ Time Complexity: O(N log N)
🔹 Problem 6: Minimum Number of Coins
📌 Find min coins to make a sum (Greedy works for canonical coin systems).
import java.util.*;
public class MinCoins {
public static int findMinCoins(int[] coins, int amount) {
Arrays.sort(coins);
int count = 0;
for (int i = coins.length - 1; i >= 0; i--) {
while (amount >= coins[i]) {
amount -= coins[i];
count++;
}
}
return count;
}
public static void main(String[] args) {
int[] coins = {1, 2, 5, 10, 20, 50, 100, 500, 1000};
System.out.println(findMinCoins(coins, 93)); // 5 (50+20+20+2+1)
}
}
✅ Time Complexity: O(N log N) (due to sorting)
🔹 Problem 7: Job Sequencing with Deadlines
📌 Maximize profit by scheduling jobs before deadlines.
import java.util.*;
class Job {
int id, deadline, profit;
Job(int i, int d, int p) { id = i; deadline = d; profit = p; }
}
public class JobSequencing {
public static int jobScheduling(Job[] jobs) {
Arrays.sort(jobs, (a, b) -> b.profit - a.profit);
int maxDeadline = 0;
for (Job job : jobs) maxDeadline = Math.max(maxDeadline, job.deadline);
int[] schedule = new int[maxDeadline + 1];
Arrays.fill(schedule, -1);
int profit = 0;
for (Job job : jobs) {
for (int d = job.deadline; d > 0; d--) {
if (schedule[d] == -1) {
schedule[d] = job.id;
profit += job.profit;
break;
}
}
}
return profit;
}
public static void main(String[] args) {
Job[] jobs = {
new Job(1, 2, 100), new Job(2, 1, 19),
new Job(3, 2, 27), new Job(4, 1, 25),
new Job(5, 3, 15)
};
System.out.println(jobScheduling(jobs)); // 142
}
}
✅ Time Complexity: O(N log N)
📊 Expedia Greedy Key Insights
- Sorting + local optimal selection is the backbone.
- Intervals (Activity/Platforms) test your timeline reasoning.
- Jump Game / Gas Station → test greedy reachability.
- Knapsack / Job Sequencing → optimization with constraints.
- Coins → must know when greedy works vs DP is required.
👉 In Blog 11, we’ll move into Graph Algorithms — a heavier topic covering BFS, DFS, Dijkstra, Kruskal, Prim, and Topological Sorting.
Dev — do you want Blog 11 to be another mega-edition like this (all graph patterns in one go) or should we split into Graph Traversal (DFS/BFS/Topo) and Shortest Path/MST (Dijkstra, Kruskal, Prim) as two blogs?
This content originally appeared on DEV Community and was authored by DevCorner2
DevCorner2 | Sciencx (2025-08-26T08:47:12+00:00) 🚀 Blog 10: Greedy Algorithms — Expedia DSA Prep. Retrieved from https://www.scien.cx/2025/08/26/%f0%9f%9a%80-blog-10-greedy-algorithms-expedia-dsa-prep/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.