Monday 3 June 2024

Priority queue medium variant leetcode question

Problem statement link: https://leetcode.com/problems/largest-values-from-labels/

Solution:

import java.util.*;


class Pair{

    int value;int type;

    public Pair(int value,int type)

    {

        this.value=value;this.type=type;

    }

}


class Solution {

    public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {

        PriorityQueue<Pair> pq=new PriorityQueue<Pair>((a,b)->(b.value-a.value));

        for(int i=0;i<values.length;i++)

        {

            pq.add(new Pair(values[i],labels[i]));

        }

        Map<Integer,Integer> mp=new HashMap<>();

        int result=0;int i=0;

        while(i<numWanted && !pq.isEmpty())

        {

            Pair p= pq.poll();

            if(mp.get(p.type)==null)

            {

                mp.put(p.type,1);

                result+=p.value;

                i+=1;

            }

            else if(mp.get(p.type)!=null && mp.get(p.type)<useLimit)

            {

                result+=p.value;

                mp.put(p.type,mp.get(p.type)+1);

                i+=1;

            }

        }

        return result;

    }

}

Good thoughtful question on Binary search on answers

Problem link:  https://leetcode.com/problems/maximize-score-of-numbers-in-ranges/description/ Solution: //import java.util.Arrays; class So...