CSES - Concert Tickets

Unofficial Editorial (C++)

Explanation

For each customer, we want to find the maximum possible ticket price they will accept from the available tickets. If the customer's maximum price is too low, so that no ticket price is below it, we can return -1. If not, we find the greatest ticket price less than or equal to the maximum price, and then remove that price as specified by the problem. We use a multiset for this.

Implementation

Time Complexity: $\mathcal{O}((n+ m)\log n)$

Copy
#include <bits/stdc++.h>

using namespace std;

// variables used for the current problem
int n, m, h, t;
multiset<int> tickets;

void solve() {
	cin >> n >> m;

Copy
import java.io.*;
import java.util.*;

public class ConcertTickets {
	public static void main(String[] args) throws IOException {
		Reader io = new Reader();
		PrintWriter pw = new PrintWriter(System.out);

		int ticketNum = io.nextInt();
		int peopleNum = io.nextInt();