All problems

Exam Revision Plan

Hard · greedy

Maya has a pile of topics to revise before her exams. You are given topics, where topics[i] = [hours, deadline] means topic i takes exactly hours hours of revision and must be finished by hour deadline to be worth anything.

Maya revises one topic at a time, with no breaks and no switching halfway, and she starts the first topic at hour 0. She chooses which topics to revise and in which order. A topic she skips costs her no time. A topic counts if it is finished at or before its deadline, so finishing exactly at the deadline is fine.

Return the largest number of topics Maya can make count.

Examples

Example 1

Input: topics = [[3, 6], [2, 5], [4, 9], [5, 12]]

Output: 3

Revise the 2-hour topic (done at hour 2), then the 3-hour topic (hour 5), then the 4-hour topic (hour 9). All three meet their deadlines. Adding the 5-hour topic as well would end at hour 14, after its deadline of 12.

Example 2

Input: topics = [[4, 4], [3, 5], [2, 6]]

Output: 2

Revising the 3-hour topic and then the 2-hour topic finishes at hours 3 and 5. The 4-hour topic cannot be added without making another topic late.

Example 3

Input: topics = [[5, 3]]

Output: 0

The only topic needs 5 hours but must be done by hour 3, so it can never count.

Constraints