Practice :
Contest Page :
Author :
CodeAsylums
Tester :
CodeAsylums
Editorialist :
CodeAsylums
DIFFICULTY:
Medium
PREREQUISITES:
Operating System Processes , Sorting
PROBLEM:
You have a list of start time of processes and end time of processes. The start and end times are shuffled, i.e. start times can be any order and end times can also be any order.You need to print the start and end time of each process in sorted order of its start time.
CONSTRAINTS:
1 <= N <= 10^5
1 <= start,end <= 10^9
QUICK EXPLANATION:
Sort both arrays, find start time and end times by using stack
EXPLANATION:
We sort both the arrays ie start and end time, so as to compare start time to the corresponding end time. Iterating through n elements if the 0th element(say) of start time array is less than the corresponding end time array element, we push that onto the stack, and as we find iterate further to find an element where start time > end time, ie where the previous start time element(stack top) had ended. We store the value, and remove it from the stack and so forth do this for n itertions
SOLUTION:
#(Hashtag)include <bits/stdc++.h>
using namespace std;
#(Hashtag)define MOD 1000000007
#(Hashtag)define maxn 100000000000017
#(Hashtag)define endl “\n”
#(Hashtag)define mk make_pair
#(Hashtag)define pll pair<ll, ll>
#(Hashtag)define vll vector
#(Hashtag)define vld vector
#(Hashtag)define vpll vector
#(Hashtag)define ff first
#(Hashtag)define ss second
#(Hashtag)define pb push_back
#(Hashtag)define o(…) if(local==‘L’) {__f(#VA_ARGS, VA_ARGS); cout<<endl;}
#(Hashtag)define Ns 1000007
typedef long long ll;
typedef long double ld;
char local = ‘O’;
template
void read(T &p)
{
cin >> p;
}
template <typename T, typename T1>
void read(pair<T, T1> &p)
{
read(p.ff);
read(p.ss);
}
template
void read(T arr[], ll n)
{
for (ll i = 0; i < n; i++)
{
read(arr[i]);
}
}
template
void read(vector &arr)
{
for (ll i = 0; i < arr.size(); i++)
{
read(arr[i]);
}
}
template
void out(T& n)
{
cout << n;
}
template <typename T, typename T1>
void out(pair<T, T1> &p)
{
cout << “(”;
out(p.ff);
cout << “,”;
out(p.ss);
cout << “)”;
}
template
void out(T arr[], ll n)
{
for (ll i = 0; i < n; i++)
{
out(arr[i]);
cout << " ";
}
}
template
void out(vector &arr)
{
cout << "[ ";
for (ll i = 0; i < arr.size(); i++)
{
out(arr[i]);
if (i!=arr.size()-1)
cout << ", ";
}
cout << " ]";
}
template
void out(set &arr)
{
for (auto i:arr)
{
out(i);
cout << " ";
}
}
template
void __f(const char* name, Arg1&& arg1) {
cout << name << " : ";
out(arg1);
}
template <typename Arg1, typename… Args>
void __f(const char* names, Arg1&& arg1, Args&&… args) {
const char *comma = strchr(names + 1, ‘,’);
cout.write(names, comma - names) << " : ";
out(arg1);
cout << " | ";
__f(comma + 1, args…);
}
void solve() {
ll n;
cin>>n;
vector<ll> a;
vector<ll> c(n);
vector<ll> b(n);
read(b);
read(c);
sort(b.begin(), b.end());
sort(c.begin(), c.end());
ll x = 0;
ll y = 0;
while(x<n || y<n) {
if(x==n) {
a.push_back(-1*c[y]);
y++;
continue;
}
if(y==n) {
a.push_back(b[x]);
x++;
continue;
}
if(b[x] > c[y]) {
a.push_back(-1*c[y]);
y++;
}
else {
a.push_back(b[x]);
x++;
}
}
vector<pair<ll, ll>> ans;
stack<ll> s;
for(auto i:a) {
if(i>0) {
s.push(i);
}
else {
ans.push_back({ s.top(), -1 * i });
s.pop();
}
}
sort(ans.begin(), ans.end());
for(auto i:ans) {
cout<<i.first<<" "<<i.second<<endl;
}
return;
}
int main()
{
#ifdef L
// local = 'L';
time_t start, end;
time(&start);
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
t = 1;
// cin>>t;
while (t--) {
solve();
}
#ifdef L
time(&end);
double time_taken = double(end - start);
cout << endl
<< endl
<< endl
<< "Time taken by program is : " << fixed
<< time_taken << setprecision(6);
cout << " sec " << endl;
#endif
}