// https://leetcode.com/discuss/interview-question/373202/amazon-oa-2019-optimal-utilization

​

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text.Json;

​

public class Program

{

    public class IdValuePair

    {

        public int Id { get; set; }

        public int Value { get; set; }

    }

​

    public class OptimalPair

    {

        public int Id1 { get; set; }

        public int Id2 { get; set; }

    }

​

    public static void GetOptimalPairs(List<IdValuePair> a, List<IdValuePair> b, int target)

    {

        var optimalPairs = new List<OptimalPair>();

        var pq = new PriorityQueue<OptimalPair, int>();

        pq.Enqueue(new OptimalPair {Id1 = 0, Id2 = 0}, 0); // initialize pq

        a.Sort((a, b) => b.Value - a.Value);

        b.Sort((a, b) => b.Value - a.Value);

        Console.WriteLine($"sorted a: {NestedListToString(a)}");

        Console.WriteLine($"sorted b: {NestedListToString(b)}");

        int currOptimalPairValue = 0;

        for (int i = 0; i < a.Count(); i++)

        {

            for (int j = 0; j < b.Count(); j++)

            {

                int pairValue = a[i].Value + b[j].Value;

                if (pairValue <= target && pairValue >= currOptimalPairValue)

                {

                    pq.Enqueue(new OptimalPair {Id1 = a[i].Id, Id2 = b[j].Id}, -(pairValue));

                    currOptimalPairValue = pairValue;

                    break;

                }

            }

        }

​

        int currPriority = int.MaxValue;

        while (pq.Count > 0)

        {

            OptimalPair op;

            int priority;

            pq.TryDequeue(out op, out priority);

            if (priority <= currPriority)

            {

                optimalPairs.Add(op);

                currPriority = priority;

            }

        }

        Console.WriteLine($"output> optimal pairs: {NestedListToString(optimalPairs)}");

    }

    public static void Main()

    {

        //int[][] a = new int[][] {new int[] {1, 2}, new int[] {2, 4}, new int[] {3, 6}};

        //int[][] b = new int[][] {new int[] {1, 2}};

        var a = new List<IdValuePair>()

        {

            new IdValuePair() {Id = 1, Value = 2},

            new IdValuePair() {Id = 2, Value = 4},

            new IdValuePair() {Id = 3, Value = 6}

        };

        var b = new List<IdValuePair>()

        {

            new IdValuePair() {Id = 1, Value = 2}

        };      

        int target = 7;

        Console.WriteLine($"input> a: {NestedListToString(a)}, b: {NestedListToString(b)}");

        GetOptimalPairs(a, b, target);

​

        //a = [[1, 3], [2, 5], [3, 7], [4, 10]]

        //b = [[1, 2], [2, 3], [3, 4], [4, 5]]

        Console.WriteLine();

        a = new List<IdValuePair>()

        {

            new IdValuePair() {Id = 1, Value = 3},

            new IdValuePair() {Id = 2, Value = 5},

            new IdValuePair() {Id = 3, Value = 7},

            new IdValuePair() {Id = 4, Value = 10}

        };

        b = new List<IdValuePair>()

        {

            new IdValuePair() {Id = 1, Value = 2},

            new IdValuePair() {Id = 2, Value = 3},

            new IdValuePair() {Id = 3, Value = 4},

            new IdValuePair() {Id = 4, Value = 5}

        };      

        target = 10;

        Console.WriteLine($"input> a: {NestedListToString(a)}, b: {NestedListToString(b)}");

        GetOptimalPairs(a, b, target);

        //a = [[1, 8], [2, 7], [3, 14]]

        //b = [[1, 5], [2, 10], [3, 14]]        

        Console.WriteLine();

        a = new List<IdValuePair>()

        {

            new IdValuePair() {Id = 1, Value = 8},

            new IdValuePair() {Id = 2, Value = 7},

            new IdValuePair() {Id = 3, Value = 14}

        };

        b = new List<IdValuePair>()

        {

            new IdValuePair() {Id = 1, Value = 5},

            new IdValuePair() {Id = 2, Value = 10},

            new IdValuePair() {Id = 3, Value = 14}

        };      

        target = 20;

        Console.WriteLine($"input> a: {NestedListToString(a)}, b: {NestedListToString(b)}");

        GetOptimalPairs(a, b, target);

        //a = [[1, 8], [2, 15], [3, 9]]

        //b = [[1, 8], [2, 11], [3, 12]]        

        Console.WriteLine();

        a = new List<IdValuePair>()

        {

            new IdValuePair() {Id = 1, Value = 8},

            new IdValuePair() {Id = 2, Value = 15},

            new IdValuePair() {Id = 3, Value = 9}

        };

        b = new List<IdValuePair>()

        {

            new IdValuePair() {Id = 1, Value = 8},

            new IdValuePair() {Id = 2, Value = 11},

            new IdValuePair() {Id = 3, Value = 12}

        };      

        target = 20;

        Console.WriteLine($"input> a: {NestedListToString(a)}, b: {NestedListToString(b)}");

        GetOptimalPairs(a, b, target);

}

    // helpers

    private static string NestedListToString<T>

    (

        List<T> nestedList,

        bool asArray = false,

        bool indented = false,

        int level = 1

    )

    {

        string openingBracket = $"{(asArray ? "[" : "{")}{(indented ? $"\n{new string('\t', level)}" : "")}";

        string closingBracket = $"{(indented ? $"\n{new string('\t', level - 1)}" : "")}{(asArray ? "]" : "}")}";

        string joinSeparator = $",{(indented ? $"\n{new string('\t', level)}" : "")}";

​

        if (typeof(T).IsValueType || typeof(T) == typeof(String))

        {

            // if elements in the list is of value type (e.g. int, decimal, bool, char) or string type

            return $"{(asArray ? "[" : "{")}{string.Join(',', nestedList)}{(asArray ? "]" : "}")}";

        }

        else if (typeof(T).IsNested)

        {

            // if elements in the list is a class type

            return $"{openingBracket}{string.Join(joinSeparator, nestedList.Select(i => JsonSerializer.Serialize(i)))}{closingBracket}";

        }

        else

        {

            // here we're still dealing with nested list and so we do a recursive call on the generic method

            // just calling the generic method and passing the nested list element causes the compiler to complain about it not being able to infer the type

            //  thus, we're doing an Invoke() on the generic method with generic argument and that worked

            var nestedListString = string.Join(joinSeparator,

                nestedList.Select(nl => typeof(Program)

                    .GetMethod("NestedListToString")

                    .MakeGenericMethod(typeof(T).GetGenericArguments()[0])

                    .Invoke(null, new object[] { nl, asArray, indented, level + 1 })).ToList());

            return $"{openingBracket}{nestedListString}{closingBracket}";

        }

    }

}