Author: SQU_Test
DIFFICULTY:
Medium
PREREQUISITES:
Greedy, Sorting pairs.
PROBLEM:
Student Muna is an undergraduate student at the University. Her final exams are approaching and she is to pass exactly n exams. Muna is a smart girl, so she will be able to pass any exam she takes on her first try. Besides, she can take several exams on one day, and in any order.
According to the schedule, a student can take the exam for the i-th subject on the day number a_i. However, Muna has arranged with each teacher and the instructor of the i-th subject allowed her to take an exam before the schedule time on day b_i (b_i < a_i). Thus, Muna can take an exam for the i-th subject either on day a_i, or on day b_i. All the instructors put the record of the exam in the student’s record book on the day of the actual exam and write down the date of the mark as number a_i.
Muna believes that it would be rather strange if the entries in the record book did not go in the order of non-decreasing date. Therefore, Muna asks you to help her. Find the minimum possible value of the day when Muna can take the last exam if she takes exams so that all the records in her record book go in the order of non-decreasing date.
EXPLANATION:
The solution is greedy. Sort the exams by increasing a_i, breaking ties by increasing b_i. Let’s consider exams in this order and try to take the exams as early as possible. Take the first exams in this order on the early day ( b_1). Move to the second exam. If we can take it on the day b_2 (i.e. b_1 ≤ b_2), do it. Otherwise, take the second exam on the day a_2. Continue the process, keeping the day of the latest exam.
TIME COMPLEXITY:
Time complexity of the solution is O(n log n) for sorting.
SOLUTIONS:
Setter’s Solution - Python
n = int(input())
e = []
for i in range(n):
e.append(list(map(int,input().split())))
e.sort()
cur = e[0][1]
for i in range(1,n):
if e[i][1] < cur:
cur = e[i][0]
else:
cur = e[i][1]
print(cur)
Setter’s Solution – C++
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int n;
scanf("%d",&n);
pair <int,int> a[n];
for(int i=0;i<n;++i)
scanf("%d %d", &a[i].first, &a[i].second);
sort(a,a+n);
int best = -1;
for(int i=0;i<n;++i){
if (a[i].second >= best){
best = a[i].second;
}
else{
best = a[i].first;
}
}
printf("%d", best);
}