amazon Optimal Utilization

Posted on | Edited on | Views:

link

Two Pointers

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// import java.util.*;
class OptimalUti {
    static List<int[]> getPairs(List<int[]> a, List<int[]> b, int target) {
        Collections.sort(a, (i,j) -> i[1] - j[1]);
        Collections.sort(b, (i,j) -> i[1] - j[1]);
        List<int[]> result = new ArrayList<>();
        int max = Integer.MIN_VALUE;
        int m = a.size();
        int n = b.size();
        int i =0;
        int j =n-1;
        while(i<m && j >= 0) {
            int sum = a.get(i)[1] + b.get(j)[1];
            if(sum > target) {
                 --j;
            } else {
                if(max <= sum) {
                    if(max < sum) {
                        max = sum;
                        result.clear();
                    }
                    result.add(new int[]{a.get(i)[0], b.get(j)[0]});
                    int index = j-1;
                    while(index >=0 && b.get(index)[1] == b.get(index+1)[1]) {
                         result.add(new int[]{a.get(i)[0], b.get(index--)[0]});
                    }
                }
                ++i;
            }
        }
        return result;
    }
}
/*
class MyClass{
    public static void main(String...s) {
        List<int[]> a=new ArrayList<>();
        a.add(new int[]{1, 2});
        a.add(new int[]{2, 4});
        a.add(new int[]{3, 6});

        List<int[]> b=new ArrayList<>();
        b.add(new int[]{1, 2});
        b.add(new int[]{2, 3});
        b.add(new int[]{3, 4});
        b.add(new int[]{4, 5});

        int targets = 7;
        
        for(int[] arr:OptimalUti.getPairs(a, b, targets)){
            System.out.println(Arrays.toString(arr));
        }
    }
}*/

TreeMap

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
30
31
32
33
34
35
36
37
38
39
//import java.util.*;
class OptimalUti {
    static List<List<Integer>> compute(int[][] a, int[][] b, int target) {
        TreeMap<Integer, List<List<Integer>>> tree = new TreeMap<>();

        for (int i=0; i<a.length; i++) {
            for (int j=0; j<b.length; j++) {
                int sum = a[i][1] + b[j][1]; 
                if (sum <= target) {
                    List<List<Integer>> list = tree.computeIfAbsent(sum, (k) -> new ArrayList<>());
                    list.add(Arrays.asList(a[i][0], b[j][0]));
                }
            }
        }
        return tree.floorEntry(target).getValue();
    }
}
/*
class MyClass{
    public static void main(String...s) {
        int[][][] As = {
            {{1, 2}, {2, 4}, {3, 6}},
            {{1, 3}, {2, 5}, {3, 7}, {4, 10}},
            {{1, 8}, {2, 7}, {3, 14}},
            {{1, 8}, {2, 15}, {3, 9}}
        };
        int[][][] Bs = {
            {{1, 2}},
            {{1, 2}, {2, 3}, {3, 4}, {4, 5}},
            {{1, 5}, {2, 10}, {3, 14}},
            {{1, 8}, {2, 11}, {3, 12}}
        };
        int[] targets = {7, 10, 20, 20};

        for (int i=0; i<4; i++) {
            System.out.println(OptimalUti.compute(As[i], Bs[i], targets[i]).toString());
        }
    }
}*/

0%