Given an exam of N problems with a time limit of T, your task is to figure out the maximum number of exam items you can complete within the time limit, given the amount of time t; each problem would take for you to solve them and the amount of points p; you can get from solving each respective problem. Some really difficult problems may as well be unsolvable; these problems will have a t; value of -1. If f you cannot solve a single problem within the time limit, then you are to say "This exam is impossible!" Input Format The first line of the input contains two space-separated integers N and T, indicating the number of problems in the exam and the exam's time limit (in minutes, rounded to the nearest minutes). N lines follow, each containing a pair of space-separated integers tį and pi, where t; is the number of minutes, rounded to the nearest minute, needed to complete the ith problem and p; is the number of points the ith problem is worth. Note that if a problem cannot be solved, it's t; value would be -1. Constraints 1≤N ≤ 105 0≤ T ≤ 10⁹ 0 ≤ti, Pi≤ 104 V ti = -1 Output Format Output consists of either a single integer n, where n is the maximum number of problems that can be solved within the given time limit T or "This exam is impossible!" (without quotes) if no problem can be solved within the given time limit T.

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Concept explainers

Question

Information is present in the screenshot and below. Based on that need help in solving the code for this problem in java. The time complexity has to be as less as possible (nlogn or n at best, no n^2). Apply greedy algorithm in the problem. Make sure both test cases return correct answers.

Sample Input 0
5 29
3 8
7 9
7 2
6 6
7 4

Sample Output 0
4

Explanation 0
You can finish the first 4 problems, which will take 3+7+7+6=23 seconds. Attempting the fifth problem will result in 23+7=30 seconds, which is greater than T=29.

6 5
6 6
7 10
9 4
9 11
10 10
10 0

Sample Output 1
This exam is impossible!

Explanation 1
None of the problems have t_i <= T = 5, so it is impossible to finish even a single problem.

The actual code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Solution {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();

String[] parts = br.readLine().trim().split(" ");
int n = Integer.parseInt(parts[0]);
int t = Integer.parseInt(parts[1]);
int[][] problems = new int[n][2];

for(int i = 0; i < n; i++) {
parts = br.readLine().trim().split(" ");
for(int j = 0; j < 2; j++){
problems[i][j] = Integer.parseInt(parts[j]);
}
}
System.out.println(solve(n,t,problems));
}

public static String solve(int n, int t, int[][] problems)
{
// compute and return answer here
}
}

Given an exam of N problems with a time limit of T, your task is to figure out the maximum number of exam
items you can complete within the time limit, given the amount of time t; each problem would take for you to
solve them and the amount of points p; you can get from solving each respective problem. Some really
difficult problems may as well be unsolvable; these problems will have a t; value of -1.
If you cannot solve a single problem within the time limit, then you are to say "This exam is impossible!"
Input Format
The first line of the input contains two space-separated integers N and T, indicating the number of problems
in the exam and the exam's time limit (in minutes, rounded to the nearest minutes).
N lines follow, each containing a pair of space-separated integers t; and p¿, where t; is the number of
minutes, rounded to the nearest minute, needed to complete the ith problem and p; is the number of points
the ith problem is worth.
Note that if a problem cannot be solved, it's t; value would be −1.
Constraints
1 ≤ N ≤ 105
0≤ T ≤ 10⁹
0 ≤ ti, Pi ≤ 10¹ V t; = −1
Output Format
Output consists of either a single integer n, where ŉ is the maximum number of problems that can be solved
within the given time limit T or "This exam is impossible!" (without quotes) if no problem can be solved within
the given time limit T.

Expert Solution

Step by step

Solved in 4 steps with 3 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions