#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/* [14:44] Baranwal, Ankur
Tesco has around 3200 stores and more than 10% of the stores have around 80 colleagues each.
In a store, a colleague can work for multiple departments. Here are shifts of a colleague in various departments:
In Bakery department: From 8 to 10
In Checkout department: From 10 to 12
In Dairy department: From 14 to 19
Given the above split of shifts, provide an API/method to return the different shifts of a colleague for the day after merging contiguous shifts. This will be exposed to the colleague in different UI and help them plan their day accordingly.
His shift timings in this case are 8 to 12 and 14 to 19. */
struct node
{
int start,end;
node(int x1,int y1)
{
start=x1;
end=y1;
}
};
bool comp(node*a,node*b)
{
if(a->start == b->start)
{
return a->end < b->end;
}
else
{
return a->start < b->start;
}
}
vector<node*> findMergedTimings(vector<node*> timings)
{
vector<node*> mergedTimings;
if(timings.size() == 0)
{
return mergedTimings;
}
sort(timings.begin(),timings.end(),comp);
mergedTimings.push_back(timings[0]);
for(int i=1;i<timings.size();i++)
{
if(mergedTimings.back()->end >= timings[i]->start)
{
mergedTimings.back()->end= max(mergedTimings.back()->end,timings[i]->end);
mergedTimings.back()->start = min(mergedTimings.back()->start,timings[i]->start);
}
else
{
mergedTimings.push_back(timings[i]);
}
}
return mergedTimings;
}
int main() {
vector<node*> timings;
timings.push_back(new node(8,10));
timings.push_back(new node(10,12));
timings.push_back(new node(14,19));
vector<node*> mergedTimings = findMergedTimings(timings);
for(int i=0;i<mergedTimings.size();i++)
{
cout<<"("<<mergedTimings[i]->start<<","<<mergedTimings[i]->end<<")"<<endl;
}
cout<<endl;
timings.clear();
timings.push_back(new node(0,8));
timings.push_back(new node(10,12));
timings.push_back(new node(14,19));
mergedTimings = findMergedTimings(timings);
for(int i=0;i<mergedTimings.size();i++)
{
cout<<"("<<mergedTimings[i]->start<<","<<mergedTimings[i]->end<<")"<<endl;
}
cout<<endl;
timings.clear();
timings.push_back(new node(0,20));
timings.push_back(new node(10,12));
timings.push_back(new node(14,19));
mergedTimings = findMergedTimings(timings);
for(int i=0;i<mergedTimings.size();i++)
{
cout<<"("<<mergedTimings[i]->start<<","<<mergedTimings[i]->end<<")"<<endl;
}
cout<<endl;
timings.clear();
mergedTimings = findMergedTimings(timings);
for(int i=0;i<mergedTimings.size();i++)
{
cout<<"("<<mergedTimings[i]->start<<","<<mergedTimings[i]->end<<")"<<endl;
}
cout<<endl;
timings.clear();
timings.push_back(new node(9,12));
timings.push_back(new node(0,8));
timings.push_back(new node(14,19));
mergedTimings = findMergedTimings(timings);
for(int i=0;i<mergedTimings.size();i++)
{
cout<<"("<<mergedTimings[i]->start<<","<<mergedTimings[i]->end<<")"<<endl;
}
return 0;
}