为了拯救因入学人数骤降,面临废弃的学校,牛牛决定成为偶像啦。当然,作为一个偶像,肯定是要上台表演的。
已知牛牛拿到了n个上台表演的机会,第i次表演的上台时间为ti时刻,需要表演mi这么长的时间。
牛牛为了提高自己的知名度,肯定要取得最多的上场次数。请问,牛牛最多能上场多少次呢?
第一行输入一个数字n(1≤n≤100000),表示牛牛获得的上台表演的机会
接下来n行,每行输入两个数字ti(1≤ti≤108)和mi(1≤mi≤108), 表示第i次表演机会的上台时间和该次表演需要的总时间(表演途中不能中断表演退出)。
牛牛最多能上场的次数。
3 1 2 3 2 5 2
3
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); } }