IVN
0%

Greedy-2

Posted on Edited on In
Symbols count in article: 5.7k Reading time ≈ 5 mins.

Greedy选编2

502. IPO

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//not clever enough!
public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
    //max profit with capital <= curCapital
    int cur=w;
    //[capital, profit]
    PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->(a[1]!=b[1] ? b[1]-a[1] : a[0]-b[0]));
    int n=profits.length;
    for (int i = 0; i < n; i++) {
        pq.offer(new int[]{capital[i],profits[i]});
    }
    while(k-->0 && !pq.isEmpty()){
        List<int[]> list=new ArrayList<>();
        while(!pq.isEmpty() && pq.peek()[0]>cur){
            list.add(pq.poll());
        }
        if(pq.isEmpty()){
            break;
        }
        int[] p=pq.poll();
        cur+=p[1];
        for (int[] arr : list) {
            pq.offer(arr);
        }
    }
    return cur;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
        int n=profits.size();
        vector<pair<int,int>> projects;
        for(int i=0; i<n; i++){
            //emplace_back is more efficient than push_back
            //instead of push_back({1, 2}) you can use emplace_back(1, 2)
            projects.emplace_back(capital[i],profits[i]);
        }
        //by default, sort by pair.first
        sort(projects.begin(),projects.end());
        //by default, biggest on top
        priority_queue<int> q;
        int idx=0;
        while(k-->0){
            while(idx<n && projects[idx].first<=w){
                q.push(projects[idx++].second);
            }
            if(q.empty()){
                break;
            }
            //int top(); void pop();
            w+=q.top();
            q.pop();
        }
        return w;
    }
};

135. Candy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int candy(int[] ratings) {
    int n=ratings.length;
    int[] arr=new int[n];
    Arrays.fill(arr,1);
    for (int i = 1; i < n; i++) {
        if(ratings[i]>ratings[i-1]){
            arr[i]=arr[i-1]+1;
        }
    }
    int res=arr[n-1];
    for (int i = n-2; i >= 0; i--) {
        if(ratings[i]>ratings[i+1]){
            arr[i]=Math.max(arr[i],arr[i+1]+1);
        }
        res+=arr[i];
    }
    return res;
}

2141. Maximum Running Time of N Computers

法一：sorting

思路：

  • use up biggest batteries first
  • spare the extra to smallest battery, raise them as much as possible
  • if still has extra, spare them to all batteries
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public long maxRunTime(int n, int[] batteries) {
    Arrays.sort(batteries);
    int len=batteries.length;
    //[len-n,len-1]
    long extra=0;
    for (int i = len - n-1; i >= 0; i--) {
        extra+=batteries[i];
    }
    long res=batteries[len-n];
    for(int i=len-n+1; i<len; i++){
        //[len-n,i-1]
        long delta=(i-len+n)*(batteries[i]-batteries[i-1]);
        if(delta<=extra){
            extra-=delta;
            res=batteries[i];
        }else{
            res+=extra/(i-len+n);
            break;
        }
    }
    if(extra>0){
        res+=extra/n;
    }
    return res;
}

思路：

  • find max
  • how to validate:
    • a large battery cannot be fully utilized, because it cannot serve 2 computers simultaneously
    • a small battery can be fully utilized
    • only need to check total power>=target or not
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public long maxRunTime(int n, int[] batteries) {
    long sum=0;
    for (int battery : batteries) {
        sum+=battery;
    }
    long left=1;
    long right=sum/n;
    while(left<right){
        //(left,right]
        long mid=(left+right+1)/2;
        long total=0;
        for (int battery : batteries) {
            total+=Math.min(battery,mid);
        }
        if(total<mid*n){
            right=mid-1;
        }else{
            left=mid;
        }
    }
    return right;
}

2808. Minimum Seconds to Equalize a Circular Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int minimumSeconds(List<Integer> nums) {
    Map<Integer,List<Integer>> map=new HashMap<>();
    for (int i = 0; i < nums.size(); i++) {
        int val=nums.get(i);
        map.putIfAbsent(val,new ArrayList<>());
        map.get(val).add(i);
    }
    int res=Integer.MAX_VALUE;
    int n=nums.size();
    for (Integer val : map.keySet()) {
        //consider all candidates
        List<Integer> list=map.get(val);
        list.add(list.get(0)+n);
        //nums[i]==nums[j]==val
        //[i,j] takes (j-i)/2 steps to equalize to val
        int cur=0;
        for(int i=0; i<list.size()-1; i++){
            cur=Math.max(cur,(list.get(i+1)-list.get(i))/2);
        }
        res=Math.min(res,cur);
    }
    return res;
}

2551. Put Marbles in Bags

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//k=1: 0,n-1
//k=2: 0,a,b,n-1, a,b must be adjacent
//k=3: 0,a,b,c,d,n-1, a,b,c,d must be adjacent
public long putMarbles(int[] weights, int k) {
    List<Integer> list=new ArrayList<>();
    int n= weights.length;
    for (int i = 0; i < n-1; i++) {
        //[0,1] to [n-2,n-1]
        list.add(weights[i]+weights[i+1]);
    }
    Collections.sort(list);
    long min=0;
    for (int i = 0; i < k-1; i++) {
        min+=list.get(i);
    }
    Collections.reverse(list);
    long max=0;
    for (int i = 0; i < k - 1; i++) {
        max+=list.get(i);
    }
    return max-min;
}

2745. Construct the Longest New String

brainteaser

1
2
3
4
5
6
7
8
9
10
public int longestString(int x, int y, int z) {
    //ab won't benefit others
    //bb + ab, still cannot be appended by bb
    if(Math.abs(x-y)<=1){
        return 2*x+2*y+2*z;
    }else{
        int a=Math.min(x,y);
        return 2*a+2*(a+1)+2*z;
    }
}

1199. Minimum Time to Build Blocks

huffman code:

  1. construct the optimal tree
  2. always merge the 2 smallest node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int minBuildTime(int[] blocks, int split) {
    //always assign larger block first
    //Arrays.sort(blocks);
    int n=blocks.length;
    //only split when necessary
    PriorityQueue<Integer> pq=new PriorityQueue<>();
    for (int i = 0; i < n; i++) {
        pq.offer(blocks[i]);
    }
    while(pq.size()>1){
        int x=pq.poll();
        int y=pq.poll();
        pq.offer(y+split);
    }
    return pq.poll();
}

1727. Largest Submatrix With Rearrangements

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public int largestSubmatrix(int[][] matrix) {
    int row=matrix.length;
    int col=matrix[0].length;
    int[][] grid=new int[row][col];
    for (int j = 0; j < col; j++) {
        for (int i = 0; i < row; i++) {
            if(matrix[i][j]!=0){
                if(i==0){
                    grid[i][j]=1;
                }else{
                    grid[i][j]=1+grid[i-1][j];
                }
            }
        }
    }
    int res=0;
    for (int i = 0; i < row; i++) {
        Arrays.sort(grid[i]);
        //[j,col-1]
        for (int j = col-1; j >= 0; j--) {
            if(grid[i][j]==0){
                break;
            }
            res=Math.max(res,grid[i][j]*(col-j));
        }

    }
    return res;
}