Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayList;
- import java.util.Scanner;
- class Heap<E extends Comparable<E>> {
- private E[] elements;
- public Heap(int size) {
- this.elements = (E[]) new Comparable[size];
- }
- int getParent(int i) {
- return (i + 1) / 2 - 1;
- }
- public E getAt(int i) {
- return this.elements[i];
- }
- int getLeft(int i) {
- return (i + 1) * 2 - 1;
- }
- int getRight(int i) {
- return (i + 1) * 2;
- }
- void setElement(int index, E elem) {
- this.elements[index] = elem;
- }
- void swap(int i, int j) {
- E tmp = this.elements[i];
- this.elements[i] = this.elements[j];
- this.elements[j] = tmp;
- }
- void adjust(int i, int n) {
- while(true) {
- if (i < n) {
- int left = this.getLeft(i);
- int right = this.getRight(i);
- int largest = i;
- if (left < n&&this.elements[left].compareTo(this.elements[i]) > 0) {
- largest = left;
- }
- if (right < n && this.elements[right].compareTo(this.elements[largest]) > 0) {
- largest = right;
- }
- if (largest != i) {
- this.swap(i, largest);
- i = largest;
- continue;
- }
- }
- return;
- }
- }
- void buildHeap() {
- for(int i = this.elements.length / 2 - 1; i >= 0; --i) {
- this.adjust(i, this.elements.length);
- }
- }
- public void heapSort() {
- this.buildHeap();
- for(int i = this.elements.length - 1; i > 0; --i) {
- this.swap(0, i);
- this.adjust(0, i);
- }
- }
- }
- class Entry implements Comparable<Entry> {
- protected int vlez;
- protected int prestoj;
- public Entry(int v, int p) {
- this.vlez = v;
- this.prestoj = p;
- }
- public int vkupno() {
- return this.vlez + this.prestoj;
- }
- public int compareTo(Entry e) {
- if (this.vlez > e.vlez) {
- return 1;
- } else {
- return this.vlez < e.vlez ? -1 : 0;
- }
- }
- }
- public class BlackFriday {
- public BlackFriday() {
- }
- public static void main(String[] args) throws Exception {
- Scanner br = new Scanner(System.in);
- int N = Integer.parseInt(br.nextLine());
- Heap<Entry> heapDrvo = new Heap(N);
- for(int i = 0; i < N; ++i) {
- String s = br.nextLine();
- String[] pom = s.split(" ");
- String[] cas = pom[0].split(":");
- int vlez = Integer.parseInt(cas[0]) * 60 + Integer.parseInt(cas[1]);
- int prestoj = Integer.parseInt(pom[1]);
- Entry nov = new Entry(vlez, prestoj);
- heapDrvo.setElement(i, nov);
- }
- heapDrvo.heapSort();
- ArrayList<Entry> lista = new ArrayList(0);
- int max = 0;
- for(int i = 0; i < N; ++i) {
- for(int j = 0; j < lista.size(); ++j) {
- if (((Entry)lista.get(j)).vkupno() < ((Entry)heapDrvo.getAt(i)).vlez) {
- lista.remove(j);
- }
- }
- lista.add((Entry)heapDrvo.getAt(i));
- if (lista.size() > max) {
- max = lista.size();
- }
- }
- System.out.println(max);
- br.close();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment