Algorithm: Greedy Problems

What is a Greedy Algorithm?

A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage.

When solving greedy problems, we always choose the next piece that offers the most obvious and immediate benefits.

A typical Greedy Algorithm problem is Huffman Tree.

And the most common solution for Greedy Algorithm are priority queue and comparator.

Huffman Tree (Huffman Coding)

Huffman Coding is a technique of compressing data to reduce its size without losing any of the details.

Huffman Coding is generally useful to compress the data in which there are frequently occurring characters.

in this article, I will use a simplified version Huffman Tree, say,

given an array, each time sum up two numbers, and put the sum back to array,

calculate the smallest sum of array.

eg. [1, 2, 3, 4]

1 + 2 = 3, then [3, 3, 4], with sum = 3

3 + 3 = 6, then [4, 6], with sum = 3 + 6

4 + 6 = 10, then sum = 3 + 6 + 10

public class HuffmanTree {
    public static getHuffmanSum(int[] arr) {
        int sum = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i: arr) {
            pq.add(i);
        }
        int first = 0, second = 0;
        int curSum = 0;
        while(pq.size() > 1) {
            first = pq.poll();
            second = pq.poll();
            
            curSum = first+second;
            
            sum += curSum;
            
            pq.add(curSum);
        }
        
        return sum;
    } 
}

Meeting Arrangement Problem

each meeting has start time and end time, cannot arrange two meetings at same time,

given a list of meeting, figure out how many meetings can be arranged

solution: sorted by the end time of meeting, then pick up the earliest one when possible.

public class Meeting {
    int startTime;
    int endTime;
}

public class MeetingComparator implements Comparator<Meeting> {
    @Override
    public int compare(Meeting m1, Meeting m2) {
        return m1.endTime - m2.endTime;
    }
}

public class MeetingArranger {
    public static int arrange(Meeting[] meetings) {
        int res = 0;
        Arrays.sort(meetings, new MeetingComparator());
        int curEndTime = 0;
        
        for(Meeting m: meetings) {
            if(m.startTime >= curEndTime) {
                curEndTime = m.endTime;
                res++;
            }
        }
        
        return res;
    }
}

Project Management Problem

each project has its cost and revenue, given the initial budget and a list of projects, some projects might be too expensive to complete, figure out the max revenue.

public class Project {
    int cost;
    int revenue;
}

public class ProjectPlanner {
    public int maxRevenue(Project[] projects, int init) {
        PriorityQueue<Project> locked = new PriorityQueue<>(new Comparator<Project>() {
            @Override
            public int compare(Project p1, Project p2) {
                return p1.cost - p2.cost;
            }
        });
        
        PriorityQueue<Project> unlocked = new PriorityQueue<>(new Comparator<Project>() {
            @Override
            public int compare(Project p1, Project p2) {
                return p2.revenue - p1.revenue;
            }
        });
         
        for(Project p: projects) {
            locked.add(p);
        }
        
        int earnedMoney = init;
        Project temp;
        while(true) {
            while(!locked.isEmpty() && locked.peek().cost <= earnedMoney) {
                unlocked.add(locked.pop());
            }
            
            if (!unlocked.isEmpty()) {
                temp = unlocked.pop();
                earnedMoney += temp.revenue - temp.cost;
            } else {
                break;
            }
            
        }
        
		return earnedMoney;
        
    }
}