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);
}
1) Use replace of TreeMap where-ever possible
2) Use faster I/O
3) Output whole result at once and not in steps..
Here is my java AC JAVA