Colas de prioridad

priority_queue<int> pq;
pq.push(7);                // [7]
pq.push(2);                // [2, 7]
pq.push(1);                // [1, 2, 7]
pq.push(5);                // [1, 2, 5, 7]
cout << pq.top() << endl;  // 7
pq.pop();                  // [1, 2, 5]
pq.pop();                  // [1, 2]
pq.push(6);                // [1, 2, 6]

PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
pq.add(7);                      // [7]
pq.add(2);                      // [7, 2]
pq.add(1);                      // [7, 2, 1]
pq.add(5);                      // [7, 5, 2, 1]
System.out.println(pq.peek());  // 1
pq.poll();                      // [7, 5, 2]
pq.poll();                      // [7, 5]
pq.add(6);                      // [7, 6, 5]

import heapq
 
pq = []
 
"""
La siguiente línea no es necesaria porque pq empieza como lista vacía. Sin
embargo, para listas de longitud mayor que 1, heapify hace falta para convertir
la lista en un heap.
"""
heapq.heapify(pq)
 
heapq.heappush(pq, 7)  # [7]
heapq.heappush(pq, 2)  # [7, 2]
heapq.heappush(pq, 1)  # [7, 2, 1]
heapq.heappush(pq, 5)  # [7, 5, 2, 1]
print(pq[0])  # 1
heapq.heappop(pq)  # [7, 5, 2]
heapq.heappop(pq)  # [7, 5]
heapq.heappush(pq, 6)  # [7, 6, 5]

#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
 
int main() {
	int N;
	cin >> N;
 
	vector<int> ans(N);
	vector<pair<pair<int, int>, int>> v(N);
 
	v.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> v[i].first.first >> v[i].first.second;
		v[i].second = i;  // store the original index
	}
	sort(v.begin(), v.end());
 
	int last_room = 0;
	using Room = pair<int, int>;
	// min heap to store departure times.
	priority_queue<Room, vector<Room>, greater<Room>> pq;
	for (int i = 0; i < N; i++) {
		if (pq.empty() || pq.top().first >= v[i].first.first) {
			last_room++;
			pq.push(make_pair(v[i].first.second, last_room));
			ans[v[i].second] = last_room;
		} else {
			// accessing the minimum departure time
			Room minimum = pq.top();
			pq.pop();
			pq.push(make_pair(v[i].first.second, minimum.second));
			ans[v[i].second] = minimum.second;
		}
	}
 
	cout << last_room << "\n";
	for (int i = 0; i < N; i++) { cout << ans[i] << " "; }
}

import java.io.*;
import java.util.*;
 
public class RoomAllocation {
	public static void main(String[] args) {
		FastIO io = new FastIO();
 
		int n = io.nextInt();
		Customer[] customers = new Customer[n];
		for (int i = 0; i < n; i++) {
			int arrival = io.nextInt();
			int departure = io.nextInt();
			customers[i] = new Customer(arrival, departure, i);
		}
 
		// sort customers by arrival time
		Arrays.sort(customers, Comparator.comparingInt(c -> c.arrival));
 
		PriorityQueue<Room> pq = new PriorityQueue<>(
		    // order rooms by departure
		    Comparator.comparingInt(r -> r.departure));
 
		int k = 0;
		// the room numbers allocated to each customer
		int[] roomAllocations = new int[n];
		// the number of the last new room we've allocated
		int lastRoom = 1;
 
		// add the first customer to the priority queue
		pq.add(new Room(customers[0].departure, lastRoom));
		roomAllocations[customers[0].index] = lastRoom;
 
		for (int i = 1; i < n; i++) {
			// find the minimum departure time
			Room min = pq.peek();
 
			if (min.departure < customers[i].arrival) {
				pq.remove();
				pq.add(new Room(customers[i].departure, min.number));
				roomAllocations[customers[i].index] = min.number;
			} else {
				lastRoom++;
				pq.add(new Room(customers[i].departure, lastRoom));
				roomAllocations[customers[i].index] = lastRoom;
			}
			k = Math.max(k, pq.size());
		}
 
		io.println(k);
		// use StringBuilder to speed up output
		StringBuilder str = new StringBuilder();
		for (int allocation : roomAllocations) { str.append(allocation).append(" "); }
		io.println(str);
		io.close();
	}
 
	static class Customer {
		int arrival, departure, index;
 
		Customer(int arrival, int departure, int index) {
			this.arrival = arrival;
			this.departure = departure;
			this.index = index;
		}
	}
 
	static class Room {
		// departure: the time that the customer occupying the room leaves
		// number: the number of the room
		int departure, number;
 
		Room(int departure, int number) {
			this.departure = departure;
			this.number = number;
		}
	}
 
	// BeginCodeSnip{FastIO}
	class FastIO extends PrintWriter {
		private InputStream stream;
		private byte[] buf = new byte[1 << 16];
		private int curChar, numChars;
 
		// standard input
		public FastIO() { this(System.in, System.out); }
		public FastIO(InputStream i, OutputStream o) {
			super(o);
			stream = i;
		}
		// file input
		public FastIO(String i, String o) throws IOException {
			super(new FileWriter(o));
			stream = new FileInputStream(i);
		}
 
		// throws InputMismatchException() if previously detected end of file
		private int nextByte() {
			if (numChars == -1) throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) { throw new InputMismatchException(); }
				if (numChars == -1) return -1;  // end of file
			}
			return buf[curChar++];
		}
 
		// to read in entire lines, replace c <= ' '
		// with a function that checks whether c is a line break
		public String next() {
			int c;
			do { c = nextByte(); } while (c <= ' ');
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = nextByte();
			} while (c > ' ');
			return res.toString();
		}
		public int nextInt() {  // nextLong() would be implemented similarly
			int c;
			do { c = nextByte(); } while (c <= ' ');
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = nextByte();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9') throw new InputMismatchException();
				res = 10 * res + c - '0';
				c = nextByte();
			} while (c > ' ');
			return res * sgn;
		}
		public double nextDouble() { return Double.parseDouble(next()); }
	}
	// EndCodeSnip
}

import heapq
import sys
 
n = int(sys.stdin.readline())
timetable = []
for customer in range(n):
	arrival, departure = map(int, sys.stdin.readline().split())
	timetable.append((arrival, departure, customer))
 
timetable.sort(key=lambda x: x[0])  # sort by arrival time
priority_queue = []  # stores pairs of (departure time, customer number)
room_numbers = [-1] * n  # to be assigned
 
for arrival, departure, customer in timetable:
	if priority_queue and arrival > priority_queue[0][0]:  # check for vacant room
		room_numbers[customer] = room_numbers[priority_queue[0][1]]
		heapq.heapreplace(priority_queue, (departure, customer))
	else:  # assign new room
		heapq.heappush(priority_queue, (departure, customer))
		room_numbers[customer] = len(priority_queue)
 
print(len(priority_queue))
print(*room_numbers)