java sorting binarySearch
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {\n\n        // 1. queries \uB97C \uC815\uB82C\uD558\uAE30 \uC704\uD574\uC11C \uAE30\uC874 index\uB97C \uD3EC\uD568\uD55C queriesWithIdx\uB85C \uC7AC\uC120\uC5B8\uD55C\uB2E4. \n        \n        // 2. queriesWithIdx\uB97C x\uAC00 \uD070 \uC21C> y\uAC00 \uD070 \uC21C\uC73C\uB85C \uC815\uB82C\uD55C\uB2E4. \n        \n        // 3. nums1 \uC744 \uC815\uB82C\uD558\uAE30 \uC704\uD574\uC11C \uAE30\uC874 index\uB97C \uD3EC\uD568\uD55C nums1WithIdx\uB85C \uC7AC\uC120\uC5B8\uD55C\uB2E4. \n        \n        // 4. nums1WithIdx\uB97C x(\uC22B\uC790)\uAC00 \uD070 \uC21C\uC73C\uB85C \uC815\uB82C\uD55C\uB2E4.\n\n        // 5. List<int[]> list = new ArrayList<int[]>();\n        //    \uD574\uB2F9 list\uB294 y\uAC12\uAE30\uC900\uC73C\uB85C \uC815\uB82C\uC774 \uB420 \uAC83\uC774\uACE0  \n        //    0: y \uAC12, 1: x+y \uAC12\uC774 \uB4E4\uC5B4\uAC08 \uC608\uC815\uC774\uB2E4. \n\n        // 6. queriesWithIdx \uB97C 0~queries.length-1 \uC73C\uB85C \uC21C\uD68C\uD558\uBA74\uC11C \n        //    x : queriesWithIdx[i][0]\n        //    y:  queriesWithIdx[i][1]\n        \n        //   a) nums1WithIdx\uB97C point \uD558\uACE0 \uC788\uB294 \uB9C8\uC9C0\uB9C9 \uC9C0\uC810\uC5D0\uC11C x\uBCF4\uB2E4 \uD06C\uAC70\uB098 \uAC19\uC740 \uC218\uB4E4\uC744 list\uC5D0 \uB123\uB294\uB2E4. \n        //     1) list\uC548\uC5D0 \uC788\uB294 sum\uC758 \uAC12 \uC911\uC5D0 \uD604\uC7AC sum(x+y)\uBCF4\uB2E4 \uC791\uC740 \uAC12\uB4E4\uC740 \uC804\uBD80 \uC0AD\uC81C \uD558\uACE0 \n        //        \n        //     2) list\uC5D0 \uB123\uAE30 \uC704\uD574 list\uB97C binarySearch\uB97C \uC774\uC6A9\uD574 \uD0D0\uC0C9\uD574\uC11C y\uAC12 \uBCF4\uB2E4 \uD06C\uAC70\uB098 \uAC19\uC740 \uACF3\uC758 index\uB97C \uCC3E\uB294\uB2E4.\n        //        index\uC5D0 \uB4E4\uC5B4\uC788\uB294 \uAC12\uC774 \uAC19\uC740 \uC22B\uC790\uBA74 max\uB9CC \uAC31\uC2E0, \uC544\uB2C8\uBA74 insert \uD574\uC900\uB2E4.\n        \n        //      \u203B list \uC124\uBA85 \n        //        list\uC5D0 \uC815\uC0C1\uC801\uC73C\uB85C \uB370\uC774\uD130\uAC00 \uB4E4\uC5B4\uAC00 \uC788\uB2E4\uBA74 \n        //        [1 10] [3 8] [5 7]  \uACFC \uAC19\uC774 y\uAC00 \uCEE4\uC9C8 \uC218\uB85D sum\uC740 \uC791\uC544\uC9C0\uACE0 \uC788\uC744 \uAC83\uC774\uB2E4. \n        \n        //        \uC608\uB97C \uB4E4\uC5B4 [2 10] [3 8] [4 5] \uC778 \uC0C1\uD0DC\uC5D0\uC11C  [5 7] \uC774\uB4E4\uC5B4\uC624\uBA74 4\uBCF4\uB2E4 \uD06C\uAC70\uB098 \uAC19\uC740 \uC218\uB4E4\uC774 \uD655\uC778\uD560 \uB54C\uB294 \n        //        [4 5] [5 7] \uB458\uB2E4 \uD655\uC778\uD558\uC5EC\uC57C \uD55C\uB2E4. \n        //        4\uBCF4\uB2E4 \uD070 \uC218\uB294 \uC5B4\uCC28\uD53C \uB354 \uD070 sum\uC744 \uAC00\uC9C4 [5 7]\uD655\uC778\uB9CC \uD544\uC694\uD558\uACE0 5\uAC00 4\uBCF4\uB2E4 \uD06C\uB2C8 [4 5] \uB294 \uD544\uC694\uAC00 \uC5C6\uB294 \uC0C1\uD0DC\uAC00 \uB41C\uB2E4.\n        //        [2 10] [3 8] [4 5(\uC0AD\uC81C)] [5 7] => [2 10] [3 8]  [5 7]\n        //            \n        //        \uB2E4\uB978 \uC608\uB97C \uB4E4\uBA74 [2 10] [3 8] [4 5] \uC778 \uC0C1\uD0DC\uC5D0\uC11C  [5 10] \uC774\uB4E4\uC5B4\uC624\uBA74 \n        //        2,3,4,5 \uB97C \uD655\uC778 \uD560 \uB54C \uCDE8\uD558\uB294 \uAC12\uC740  [5 10] \uC774 \uB41C\uB2E4.\n        //        [2 10(\uC0AD\uC81C)] [3 8(\uC0AD\uC81C)] [4 5(\uC0AD\uC81C)] [5 10] => [5 10]\n\n        //   b) a)\uC5D0\uC11C \uAD6C\uD55C max\uAC12\uC744 result[queriesWithIdx[i][2]] \uC5D0 \uB123\uC5B4\uC900\uB2E4.\n        //      \u203B \uC815\uB82C\uC744 \uD588\uAE30 \uB54C\uBB38\uC5D0 query\uC758 index\uAC00 \uD2C0\uC5B4\uC838 \uC788\uB294 \uC0C1\uD0DC\n\n        // 7. result \uBC18\uD658\n\n        \n        int queriesWithIdx[][] = new int[queries.length][3];\n\n        for(int i = 0; i < queries.length; i++) {\n            queriesWithIdx[i][0] = queries[i][0];\n            queriesWithIdx[i][1] = queries[i][1];\n            queriesWithIdx[i][2] = i;\n        }\n        \n        Arrays.sort(queriesWithIdx, new Comparator<int[]>() {\n\n            @Override\n            public int compare(int[] arg0, int[] arg1) {\n                return arg1[0]==arg0[0]?arg1[1]-arg0[1]:arg1[0]-arg0[0];\n            }\n            \n        });\n\n        int n = nums1.length;\n        int nums1WithIdx[][] = new int[n][2];\n\n        for(int i = 0; i < n; i++) {\n            nums1WithIdx[i][0] = nums1[i];\n            nums1WithIdx[i][1] = i;\n        }\n\n        Arrays.sort(nums1WithIdx, new Comparator<int[]>() {\n            @Override\n            public int compare(int[] arg0, int[] arg1) {\n                return arg1[0]-arg0[0];\n            }\n        });\n\n\n        int result[] = new int[queries.length];\n        int nums1idx = 0;\n\n        List<int[]> list = new ArrayList<int[]>();\n\n        for(int i = 0; i < queriesWithIdx.length; i++) {\n           int x = queriesWithIdx[i][0];\n           int y = queriesWithIdx[i][1];\n           int originIdx = queriesWithIdx[i][2];\n\n            while(nums1idx < nums1WithIdx.length) {\n                \n                if ( nums1WithIdx[nums1idx][0] >= x ) {\n                    int insertY = nums2[nums1WithIdx[nums1idx][1]];\n                    int sum = nums1WithIdx[nums1idx][0] + insertY;\n                    \n                    int removeIdx = 0;\n                    while(list.size() > 0 && removeIdx < list.size() ) {\n                        if ( list.get(removeIdx)[1] < sum ) list.remove(removeIdx);\n                        else {\n                            removeIdx++;\n                        }\n                    }\n\n                    int idx = binarySearchUpper(list, insertY);\n                    if ( list.size() == idx ) {\n                        list.add(idx, new int[]{insertY, sum});\n                    } else{\n                        if ( list.get(idx)[1] < sum ) {\n                            if ( list.get(idx)[0] == insertY) {\n                                list.set(idx, new int[]{insertY, sum});\n                            } else{\n                                list.add(idx, new int[]{insertY, sum});\n                            }\n                            \n                        }\n                    }\n                    \n                } else {\n                    break;\n                }\n                nums1idx++;\n            }\n            int idx = binarySearchUpper(list, y);\n\n            if ( idx == list.size() ) result[originIdx] = -1;\n            else {\n                result[originIdx] = list.get(idx)[1];\n            }\n        }\n\n\n        // for(int i = 0; i < result.length; i++) System.out.print(result[i] + " "); System.out.println();\n\n        return result;\n    }\n\n    private int binarySearchUpper(List<int[]> list, int target) {\n        int start = 0;\n        int end = list.size();\n        int mid;\n        \n        while(start < end) {\n            mid = (start+end)/2;\n\n            if ( list.get(mid)[0] >= target) {\n                end = mid;\n            } else{\n                start = mid+1;\n            }\n        }\n\n        return end;\n    }\n}\n```
['Binary Search', 'Sorting', 'Java']