Skip to main content

Greedy Method

Greedy Algorithm

Greedy Algorithm

Greedy Algorithm

  • Make choice that looks best at the moment
  • Never reconsider earlier choices
  • Hope that the choice will lead to global optimal solution

Activity Selection Problem

  • input: n activities with start and finish times
  • output: maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a time

Greedy Choice

  • Choose the activity that ends first

Running time: O(nlogn) (Sort first)

When Greedy Works

  • When optimal substructure property holds
    • Greedy activity selection algorithm exploits a naturaal sub-problem structure: A[i] = number of activities you can do after activity i

Scheduling

  • n tasks, task i takes tit_i time, for every hour that passes until task i is completed, you lose wiw_i dollars

  • Goal: schedule tasks to minimize total loss

Greedy Choice

  • Consider two tasks a and b, a takes x hours, costs z dollars, b takes y hours, costs w dollars

  • cost(A then B) = xz + (x+y)w = x(z+w) + yw

  • cost(B then A) = yw + (x+y)z = xz + y(z+w)

  • Greedy choice: schedule tasks with the biggest wi/tiw_i/t_i.

Huffman Codes

  • Variable-length encoding

  • Prefix-free code: no codeword is a prefix of another codeword

  • Goal: minimize total encoding length

Greedy Choice

  • Merge two least frequent symbols

  • Running time: O(nlogn)

Leetcode examples

  1. Maximum Units on a Truck
class Solution {
public:
    int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
        sort(boxTypes.begin(),boxTypes.end(),[](vector<int>a,vector<int>b){
            return a[1]>b[1];
        });
        int ret=0;
        for(int i=0;i<boxTypes.size();++i){
            if(boxTypes[i][0]<truckSize){
                ret += boxTypes[i][0]*boxTypes[i][1];
                truckSize -= boxTypes[i][0];
            }else{
                ret += truckSize*boxTypes[i][1];
                break;
            }
        }
        return ret;
    }
};
  1. Maximum Number of Events That Can Be Attended
class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        sort(events.begin(), events.end());
        priority_queue<int, vector<int>, greater<int>> pq;
        int i = 0, res = 0, n = events.size();
        for (int d = 1; d <= 100000; ++d) {
            while (i < n && events[i][0] == d) {
                pq.push(events[i++][1]);
            }
            while (!pq.empty() && pq.top() < d) {
                pq.pop();
            }
            if (!pq.empty()) {
                pq.pop();
                ++res;
            }
        }
        return res;
    }
};

Comments

Post a Comment

Popular posts from this blog

Tries

Tries Tries Tries and Patricia Tries Motivation: The autocomplete feature in a text editor. We have a dictionary of words, and we want to find all the words that start with a given prefix. The data structure we use to store the dictionary is called a trie. Each edge is labeled with a character. Some nodes are marked as terminal nodes. By convention, children of a node are ordered alphabetically. A preordering traversal of the trie yields the words in the dictionary in alphabetical order. The total length of our text strings is m and the length of our pattern string is n . Time to build the trie: O(m) Time to search for a pattern: O(n) How long does it take to find all the words that start with a given prefix? The $ symbol is called the sentinel or marker, add this to the end of each word. It is used to mark the end of a word, it precedes all other characters in the alphabet....
Post a Comment
Read more

Recap on BFS, DFS and Strongly Connected Components

graph graph DFS topological sort considering the dependencies between tasks, we can use topological sort to find the order of tasks. def topological_sort ( graph ): visited = set () stack = [] for node in graph: if node not in visited: dfs(graph, node, visited, stack) return stack[::- 1 ] def dfs ( graph, node, visited, stack ): visited.add(node) for neighbor in graph[node]: if neighbor not in visited: dfs(graph, neighbor, visited, stack) stack.append(node) if A -> B then B.finishtime < A.finishtime, that's why we need to reverse the stack. Topological Sorting on a DAG do DFS on the graph when a node is finished, insert it into the front of a linked list Another use of DFS is in-order traversal of a binary tree . BFS BFS is used to find the shortest path in an unweighted graph . we can...
Post a Comment
Read more

Balanced Trees

Balanced Trees Balanced Trees Balanced search trees are among the most useful and versatile data structures. Many programming languages include balanced search trees in their standard libraries. e.g. C++: std::map , Java: TreeMap , Python: dict , etc. Many advanced data structures are layered on top of balanced search trees.. A quick BST recap A binary search tree is a binary tree where each node has a key and a value, and the following properties hold: Each node in the BST stores a key, and optinally, some information associated with the key. The keys in the left subtree are less than the key in its parent node, and the keys in the right subtree are greater than the key in its parent node. The height of a BST is the number of nodes on the longest path from the root to a leaf. A tree with one node has height 0, A tree with no nodes has height -1. Deleting from a BST Deleting a n...
Post a Comment
Read more