1090. Largest Values From Labels

1090. Largest Values From Labels C# Try to solve using greedy algorithm practice in 2019

It is one of medium level algorithms in the contest. The greedy algorithm may work out fine.

Here are highlights:

1. Use SortedDictionary to save all values and their label into SortedDictionary, the key of hashMap is the value, the value of hashMap is list of labels. Since the same value for same label may have duplicate, List is used to store labels;
2. Get all keys in SortedDictionary and save into the array; Iterate one by one using descending order;
3. Fail test case II (see function RunTestcase2()), I have to learn how to break two loops instead of one.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _1090_largest_value_from_labels
{
    class Program
    {
        static void Main(string[] args)
        {
            RunTestcase2();
        }

        public static void RunTestcase1()
        {
            var values = new int[] { 5, 4, 3, 2, 1 };
            var labels = new int[] { 1, 1, 2, 2, 3 };

            var result = LargestValsFromLabels(values, labels, 3, 1);
            Debug.Assert(result == 9);
        }

        public static void RunTestcase2()
        {
            var values = new int[] { 5, 4, 3, 2, 1 };
            var labels = new int[] { 1, 3, 3, 3, 2 };

            var result = LargestValsFromLabels(values, labels, 3, 2);
            Debug.Assert(result == 12);
        }

        /// <summary>
        /// 1090 largest value from labels
        /// Use greedy algorithm to solve the problem
        /// Try to simplify the algorithm and do not think generic case
        /// </summary>
        /// <param name="values"></param>
        /// <param name="labels"></param>
        /// <param name="num_wanted"></param>
        /// <param name="use_limit"></param>
        /// <returns></returns>
        public static int LargestValsFromLabels(int[] values, int[] labels, int num_wanted, int use_limit)
        {
            var sortedMap = new SortedDictionary<int, List<int>>();

            var length = values.Length;
            for (int i = 0; i < length; i++)
            {
                var key = values[i];
                var value = labels[i];

                if (!sortedMap.ContainsKey(key))
                {
                    sortedMap.Add(key, new List<int>());
                }

                sortedMap[key].Add(value);
            }

            var usedCount = new Dictionary<int, int>();

            int index = 0;
            var numbers = sortedMap.Keys.ToArray();
            length = numbers.Length;
            var sum = 0;
            var breakLoops = false;
 
            for (int i = length - 1; i >= 0; i--)
            {
                var key  = numbers[i];
                var list = sortedMap[key];

                foreach (var item in list)
                {
                    if (!usedCount.ContainsKey(item))
                    {
                        usedCount.Add(item, 0);
                    }

                    if (usedCount[item] < use_limit)
                    {
                        index++;
                        sum += key;

                        usedCount[item]++;

                        if (index == num_wanted)
                        {
                            breakLoops = true;
                            break;  // there are two loops 
                        }
                    }
                }

                if (breakLoops)
                    break; // caught by online judge, test case 2
            }

            return sum; 
        }
    }
}