I was trying to solve This_CSES_problem , in which i tried 2 approaches...
1) Sorted first array , then applying binary search on this array (result — TLE )
2) Applied TreeMap , and returned map.floorKey() (result — TLE )
can you help me out?
First_approach
public static void main(String[] args) { FastReader scn = new FastReader(); int n = scn.nextInt(); int m = scn.nextInt(); ArrayList<Long> tickets = new ArrayList<>(); ArrayList<Long> max_price = new ArrayList<>(); for (int l = 0; l < n; l++) { tickets.add(scn.nextLong()); } for (int l = 0; l < m; l++) { max_price.add(scn.nextLong()); } Collections.sort(tickets); for (int i = 0; i < m; i++) { int index = 0; int answer = search(max_price.get(i), tickets, index); if (answer == -1) { System.out.println(-1); } else { System.out.println(tickets.get(answer)); tickets.remove(answer); } } } static int search(long val , ArrayList<Long> al , int index) { int i = -1; int j = al.size(); while (i < j - 1) { int mid = (i + j) / 2; if (al.get(mid) > val ) { j = mid; } else { i = mid; } } return i; }
Second_Approach
FastReader scn = new FastReader(); int n = scn.nextInt(); int m = scn.nextInt(); TreeMap<Long, Integer> prices = new TreeMap<>(); long[] bids = new long[m]; for (int l = 0; l < n; l++) { long price = scn.nextLong(); if (prices.containsKey(price)) { prices.put(price, prices.get(price) + 1); } else { prices.put(price, 1); } } for (int l = 0; l < m; l++) { bids[l] = scn.nextLong(); Long answer = prices.floorKey(bids[l]); if (answer != null) { int val = prices.get(answer); if (val > 1) { prices.put(answer, val - 1); System.out.println(answer); } else { prices.remove(answer); System.out.println(answer); } } else { System.out.println(-1); }