Greedy Algorithms in TheAlgorithms/Java: A Complete Guide with Code Examples

TheAlgorithms/Java repository hosts over 15 production-ready greedy algorithm implementations in the com.thealgorithms.greedyalgorithms package, including Activity Selection, Fractional Knapsack, Job Sequencing, and Optimal File Merging, all structured as final utility classes with static method APIs.

The greedy algorithm paradigm makes locally optimal choices at each step to achieve globally optimal solutions for specific problem structures. In the TheAlgorithms/Java repository, these implementations reside in src/main/java/com/thealgorithms/greedyalgorithms, offering canonical examples of scheduling, resource allocation, and optimization problems solved via greedy strategies.

Activity Selection: Maximizing Compatible Events

The Activity Selection problem demonstrates the classic greedy approach to interval scheduling. The implementation in ActivitySelection.java selects the maximum number of non-overlapping activities by always choosing the activity that finishes earliest.

The core method activitySelection(int[] startTimes, int[] endTimes) first constructs a sortable data structure containing activity indices, start times, and end times. It then sorts by finish time and iterates once, adding an activity to the result ArrayList<Integer> only if its start time is greater than or equal to the finish time of the previously selected activity.

int[] start = {1, 3, 0, 5, 8, 5};
int[] end   = {2, 4, 6, 7, 9, 9};

ArrayList<Integer> chosen = ActivitySelection.activitySelection(start, end);
System.out.println("Selected activity indices: " + chosen);
// Output: [0, 1, 3, 4]

Source: [src/main/java/com/thealgorithms/greedyalgorithms/ActivitySelection.java](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/ActivitySelection.java)

Fractional Knapsack: Value-to-Weight Optimization

The Fractional Knapsack implementation solves the continuous knapsack problem where items can be broken into fractions. Located in FractionalKnapsack.java, this algorithm maximizes total value by sorting items by value-to-weight ratio in descending order.

The method fractionalKnapsack(int[] weight, int[] value, int capacity) calculates ratios, sorts them using Arrays.sort with a custom comparator, then greedily fills the knapsack. It takes whole items while they fit, then takes a fractional portion of the next item if space remains.

int[] weights = {10, 20, 30};
int[] values  = {60, 100, 120};
int capacity  = 50;

int maxValue = FractionalKnapsack.fractionalKnapsack(weights, values, capacity);
System.out.println("Maximum value = " + maxValue);   // → 240

Source: [src/main/java/com/thealgorithms/greedyalgorithms/FractionalKnapsack.java](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/FractionalKnapsack.java)

Job Sequencing with Deadlines

Job Sequencing in JobSequencing.java schedules jobs to maximize profit when each job has a deadline and profit associated with it. The greedy strategy sorts jobs by profit in descending order, then places each job in the latest available time slot before its deadline.

The implementation uses a static inner class Job to encapsulate job properties. The method findJobSequence(ArrayList<Job> jobs, int size) creates a Boolean[] slots array to track occupied time slots and an int[] result array to store the sequence of job IDs.

ArrayList<JobSequencing.Job> jobs = new ArrayList<>();
jobs.add(new JobSequencing.Job(1, 4, 20));
jobs.add(new JobSequencing.Job(2, 1, 10));
jobs.add(new JobSequencing.Job(3, 1, 40));
jobs.add(new JobSequencing.Job(4, 1, 30));

int[] sequence = JobSequencing.findJobSequence(jobs, jobs.size());
System.out.println("Job sequence: " + Arrays.toString(sequence));

Source: [src/main/java/com/thealgorithms/greedyalgorithms/JobSequencing.java](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/JobSequencing.java)

Optimal File Merging with Min-Heaps

The Optimal File Merging problem minimizes the total cost of merging files, where the cost of merging two files equals the sum of their sizes. The implementation in OptimalFileMerging.java uses a min-heap (PriorityQueue<Integer>) to always merge the two smallest available files.

The method minMergeCost(int[] files) inserts all file sizes into the priority queue, then repeatedly polls the two smallest elements, sums them, adds the sum back to the queue, and accumulates the total cost.

int[] files = {4, 3, 2, 6};

int minCost = OptimalFileMerging.minMergeCost(files);
System.out.println("Minimum merge cost = " + minCost);   // → 29

Source: [src/main/java/com/thealgorithms/greedyalgorithms/OptimalFileMerging.java](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/OptimalFileMerging.java)

Additional Greedy Implementations

The repository contains several other greedy algorithms demonstrating the paradigm's versatility across different problem domains:

• MinimumWaitingTime.java – Sorts query times to minimize total waiting time using Arrays.sort.
• StockProfitCalculator.java – Tracks the minimum price seen so far in a single pass to calculate maximum possible profit.
• KCenters.java – Implements a 2-approximation for the facility location problem using farthest-first traversal.
• GaleShapley.java – Solves the stable marriage problem through greedy proposals from one set to another.
• MergeIntervals.java – Sorts intervals by start time and greedily merges overlapping ranges.
• EgyptianFraction.java – Decomposes fractions into unit fractions by repeatedly subtracting the largest possible unit fraction.
• CoinChange.java – Greedy coin selection for canonical coin systems.
• BinaryAddition.java – Bit-wise addition with greedy carry propagation.
• BandwidthAllocation.java – Allocates bandwidth in descending order of demand.
• DigitSeparation.java – Separates even and odd digits while preserving order.

Architectural Patterns in the Repository

All greedy algorithm implementations in TheAlgorithms/Java follow consistent design patterns that ensure thread-safety and ease of use:

Stateless Utility Design – Every class is declared final with a private constructor to prevent instantiation. The public API consists entirely of static methods, making the implementations thread-safe and accessible without object creation.

Standard Library Integration – The code leverages Java's collections framework extensively:

• Arrays.sort() and Collections.sort() with custom Comparator objects for ordering
• PriorityQueue for heap-based algorithms like Optimal File Merging
• ArrayList for dynamic result collection

Separation of Concerns – Input validation, core greedy logic, and result construction are cleanly separated. For example, FractionalKnapsack.fractionalKnapsack first calculates ratios, then sorts, then iterates to fill capacity.

Summary

• TheAlgorithms/Java provides 15+ greedy algorithm implementations in the com.thealgorithms.greedyalgorithms package.
• Each algorithm follows a utility class pattern with static methods, private constructors, and final class declarations.
• Core implementations include Activity Selection, Fractional Knapsack, Job Sequencing, and Optimal File Merging, utilizing sorting and priority queues.
• The repository demonstrates greedy techniques across scheduling, resource allocation, graph matching, and numeric manipulation domains.
• All implementations leverage the Java Collections Framework for sorting and heap operations, ensuring efficient O(n log n) complexity where applicable.

Frequently Asked Questions

What is the package structure for greedy algorithms in TheAlgorithms/Java?

All greedy algorithm implementations reside in the com.thealgorithms.greedyalgorithms package under src/main/java/com/thealgorithms/greedyalgorithms/. This organizational structure separates greedy algorithms from other algorithmic paradigms like dynamic programming and graph algorithms, making it easy to locate specific implementations such as ActivitySelection.java or FractionalKnapsack.java.

How does the Fractional Knapsack implementation handle the fractional part of items?

The FractionalKnapsack.fractionalKnapsack method sorts items by value-to-weight ratio in descending order. It iterates through the sorted items, adding the full value of items that fit completely within the remaining capacity. When the remaining capacity is less than the next item's weight, it calculates the fraction of that item that fits (remaining capacity divided by item weight), multiplies by the item's value, and adds this partial value to the total before returning the maximum achievable value.

Are these greedy algorithms thread-safe?

Yes, the greedy algorithm implementations in TheAlgorithms/Java are thread-safe by design. Each algorithm class is declared final with a private constructor, preventing instantiation and subclassing. The public API consists solely of static methods that operate on primitive arrays or collection parameters passed by the caller. Since no instance state is maintained and all local variables are stack-allocated during method execution, multiple threads can safely invoke these static methods concurrently without synchronization concerns.

What is the time complexity of the Activity Selection algorithm in this repository?

The ActivitySelection.activitySelection method runs in O(n log n) time complexity, where n is the number of activities. This complexity arises from the initial sorting step, which uses Arrays.sort or Collections.sort to order activities by finish time. The subsequent iteration through the sorted activities to select compatible events runs in linear O(n) time. The space complexity is O(n) to store the sorted activity indices and the result list.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}