牛牛偶像养成记

[编程题]牛牛偶像养成记

热度指数：682 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

为了拯救因入学人数骤降，面临废弃的学校，牛牛决定成为偶像啦。当然，作为一个偶像，肯定是要上台表演的。

已知牛牛拿到了n个上台表演的机会，第i次表演的上台时间为t_i时刻，需要表演m_i这么长的时间。

牛牛为了提高自己的知名度，肯定要取得最多的上场次数。请问，牛牛最多能上场多少次呢？

输入描述:

第一行输入一个数字n(1≤n≤100000)，表示牛牛获得的上台表演的机会
接下来n行，每行输入两个数字t_i(1≤ti≤10⁸)和m_i(1≤m_i≤10⁸), 表示第i次表演机会的上台时间和该次表演需要的总时间（表演途中不能中断表演退出）。

输出描述:

牛牛最多能上场的次数。

示例1

输入

输出

算法知识视频讲解

Java

刘禅挥泪斩孔明

import java.util.*;
public class Main implements Comparable<Main> {//See Main as Act
  int startTime, endTime;

  Main(int startTimeInit, int duration) {
    this.startTime = startTimeInit;
    this.endTime = startTimeInit + duration;
  }

  public int compareTo(Main other) {return this.endTime - other.endTime;}

  public static void main(String[] args) {
    PriorityQueue<Main> pq = new PriorityQueue<>();
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt(), cnt = 0, lastEndTime = 0;

    while (n-- != 0)
      pq.add(new Main(sc.nextInt(), sc.nextInt()));
    while (pq.size() != 0) {
      if (pq.peek().startTime >= lastEndTime) {
        cnt++;
        lastEndTime = pq.peek().endTime;
      }
      pq.poll();
    }
    System.out.println(cnt);
  }
}

发表于 2018-06-28 23:49:37 回复(0)