Concert Tickets, sorting and searching problem

Question

There are n concert tickets available, each with a certain price. Then, m customers arrive, one after another. Each customer announces the maximum price he or she is willing to pay for a ticket, and after this, they will get a ticket with the nearest possible price such that it does not exceed the maximum price.

Input

The first input line contains integers n and m: the number of tickets and the number of customers.

The next line contains n integers h1,h2,…,hn: the price of each ticket.

The last line contains m integers t1,t2,…,tm: the maximum price for each customer.

Output

Print, for each customer, the price that they will pay for their ticket. After this, the ticket cannot be purchased again.

If a customer cannot get any ticket, print −1.

Constraints

 1 ≤ n, m ≤ 2⋅10^5

 1 ≤ hi, ti ≤ 10^9

Example

Input:
5 3
5 3 7 8 5
4 8 3

Output:
3
8
-1

My approach is to sort all h1, h2, ... hn then use binary search for each ti and will mark the chosen h as inf. this will be roughly done in nlog(n) + mlog(n). Is there any better idea to do it.

I implemented the code as:

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector<ll> v(n);
    ll p;
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < m; i++)
    {
        cin >> p;
        if (p < v.front())
            cout << -1 << "\n";
        else
        {   if(p>v.back()){
            cout<<v.back()<<"\n";
            v.pop_back();
        }else{
            auto it = upper_bound(v.begin(), v.end(), p);
            cout << *(it-1) << "\n";
            v.erase(it - 1);
        }
        }
    }
}

it is not executing in the limited time.

Answer 1

This can be solved using a data structure like tree map.

For each fixed price of ticket i.e. h[i] put them in a tree map with the count as value. Tree map ensures the keys inserted are in order. So for example, for the input in question, the map will look like :

3 -> 1
5 -> 2
7 -> 1
8 -> 1

Then in this map, search for the user's bid using binary search on the tree map's key set.

In Java's treemap you could use floorKey method to get the greatest key in the map less than or equal to the key you are looking for. The time complexity is O(log(n)) for this method because treemap in Java uses a Red Black Tree implementation.

Once you find a key, decrease its value by 1, if its value is 0 remove the key.

Do this with each user's bid. Overall time complexity is O(nlog(n)).

Code in java would be ( not tested ) :

private int[] getUserPrices(int[] prices, int[] bids) {
    TreeMap<Integer, Integer> tree = new TreeMap<>();
    for ( int price : prices ) {
      if ( tree.containsKey(price) ) {
         tree.put(price, tree.get(price) + 1);
      } else {
         tree.put(price, 1);
      }
    }

    int[] result = new int[bids.length];
    for ( int i = 0; i < bids.length; i++ ) {
       Integer k = tree.floorKey(bids[i]);
       if ( k != null ) {
          result[i] = k;
          int value = tree.get(k);
          if ( value-1 > 0 ) {
            tree.put(k, value-1);
          } else {
            tree.remove(k);
          }
       } else {
         result[i] == -1;
       }
    }

    return result;
}

Answer 2

In your approach, the time complexity is O(n^2) in the worst case, because of the line

v.erase(it - 1);

Here is a better approach

int main()
{
    int n, m;
    cin >> n >> m;
    int x;
    set<array<int, 2>> s;
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        s.insert({x, i});
    }
    for (int i = 0; i < m; i++)
    {
        cin >> x;
        auto it = s.lower_bound({x + 1, 0});
        if (it != s.begin())
        {
            it--;
            cout << (*it)[0] << "\n";
            s.erase(it);
        }
        else
        {
            cout << "-1\n";
        }
    }
    cout << endl;
}

You can use sets in this case, for better time complexity.

Answer 3

For JAVA readers...

        Scanner scn = new Scanner(System.in);
        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++) {     // filling the TreeMap
            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++) {     // Calculating Answer for each query
            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);

            }

        }

Answer 4

here is the solutioin using "multiset"

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
void solve()

{
    int n,m;
    cin>>n>>m;
    multiset<int>a;
    for(int i=0;i<n;i++)
    {
        int temp;
        cin>>temp;
        a.insert(temp);
    }
    while (m--)
    {
        int t;
        cin>>t;
        auto it=a.upper_bound(t);
        if(it==a.begin())
        {
            cout<<"-1"<<endl;
        }
        else 
        {
            cout<<*(--it)<<endl;
            a.erase(it);
        }
    }
    
    return ;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    int tt=1;
    // cin>>tt;
    while(tt--)
    {
        solve();
    }
    return 0;
}