Here are some scenarios where can use Greedy algorithms directly. These are classified into a few categories:
Optimization
Optimisation with absolute differences
When we need to find a target \(T\) in an array \(a\) that minimises cost, we can use the following heuristics:
- Problems where the cost is \(∑∣a_i−T∣\) → minimized by the median.
- Problems where the cost is \(∑(a_i−T)^2\) → minimized by the mean.
This extends to the following more general case of:
- Sum of distances in Manhattan metric → median (per dimension)
- Sum of distances in Euclidean metric → mean (per dimension)
Scheduling
This works well because many scheduling problems have a structure where local optimal choices lead to global optimality.
Interval Scheduling (Activity Selection)
Look for problems where tasks have start and end times, and the goal is to maximize the number of tasks without overlap.
The greedy solution would involve:
- Sort tasks by earliest finish time.
- Iteratively select the next task that starts after the last chosen task finishes.
An example problem would be scheduling the maximum number of non-overlapping meetings in a single room.
Job Sequencing with Deadlines
Tasks have deadlines and profits, and the objective is to maximize profit while respecting deadlines.
The greedy solution would involve:
- Sort jobs by profit (descending).
- Place each job in the latest available slot before its deadline.
An example problem would be scheduling advertisements where each ad has a deadline and profit, and only one ad can run at a time.
Minimizing Lateness
Problems where lateness is defined as \(\max(0, \text{finish time} - \text{deadline})\), and the goal is to minimize maximum lateness.
The greedy solution would involve:
- Sort jobs by earliest deadline first (EDF).
- Execute them in that order.
An example problem would be delivering packages where each has a deadline, and lateness is measured as how late the delivery is.
CPU Scheduling (Operating Systems)
Tasks are processes with burst times or priorities, and the goal is to optimize CPU utilization or waiting time.
The greedy solution would use either of the following strategies:
- Shortest Job First (SJF): Pick the job with the shortest burst time.
- Priority Scheduling: Pick the job with the highest priority.
- Round Robin: Rotate jobs in time slices (not greedy, but related).
The choice depends on the metric we are trying to optimize for. One example would be scheduling processes in an operating system to minimize average waiting time.