qasim.hasnain13
BAN USERComplexity will be O(n)
- qasim.hasnain13 May 13, 2015#include "iostream"
#include "map"
#include "set"
#include "vector"
using namespace std;
vector<int>& findOverLappingJobs(multimap<int,int>& jobs, set<int>& startTime)
{
vector<int>* overLappingPairs = new vector<int>;
for(set<int>::iterator itrSet = startTime.begin(); itrSet!= startTime.end(); ++itrSet)
{
auto itrRange = jobs.equal_range(*itrSet);
int max = 0;
int temp = 0;
for(auto itrMap = itrRange.first; itrMap != itrRange.second; ++itrMap)
{
overLappingPairs->push_back(itrMap->first);
overLappingPairs->push_back(itrMap->second);
temp = itrMap->second - itrMap->first;
if(temp > max)
{
max = temp;
}
}
max += *itrSet;
for(int i = *itrSet + 1; i <= max; ++i)
{
startTime.erase(i);
auto itrRange = jobs.equal_range(i);
for(auto itrMap = itrRange.first; itrMap != itrRange.second; ++itrMap)
{
overLappingPairs->push_back(itrMap->first);
overLappingPairs->push_back(itrMap->second);
}
}
overLappingPairs->push_back(-1);
}
return *overLappingPairs;
}
int _tmain(int argc, _TCHAR* argv[])
{
int numberOfJobs = 0;
cin >> numberOfJobs;
multimap<int, int> jobs;
set<int> startTime;
int start;
int end;
for(int i = 0; i < numberOfJobs; ++i)
{
cin >> start;
cin >> end;
jobs.insert(make_pair(start,end));
startTime.insert(start);
}
vector<int> result = findOverLappingJobs(jobs,startTime);
for(auto itr = result.begin(); itr != result.end(); ++itr)
{
if(*itr == -1)
{
cout << endl;
continue;
}
cout << "[" << *itr;
cout << "," << *(++itr) << "]";
}
delete &result;
return 0;
}
- qasim.hasnain13 May 13, 2015yes it will. i intend to store the starting time in a set and will use a multimap to store starting and ending time.
- qasim.hasnain13 May 13, 2015I think we need to take into consideration both the starting time and the larger value of execution time for a given start time.
eg : - let us take all the jobs started at time 1
[1,2][1,5][1,6]
the largest time for which any job starting at 1 executed = 5
at this point we have to consider all the jobs whose starting time lies between 1 to 5
i.e any job that starts at 2, 3, 4 ,5, 6 also overlaps.
void printPattern()
{
int k = 1;
auto i = 0;
for(; i <= 4; ++i)
{
int l = 0;
for(auto j = 0; j <= i; ++j)
{
if(i == j)
{
cout << j + k << endl;
++l;
}
else
{
cout << j + k << "*";
++l;
}
}
k = k + l;
}
k = k - i;
for(auto i = 4; i >= 0; --i)
{
int l = 0;
for(auto j = 0; j <= i; ++j)
{
if(i == j)
{
cout << j + k << endl;
++l;
}
else
{
cout << j + k << "*";
++l;
}
}
k = k - l + 1;
}
}
- qasim.hasnain13 April 05, 2015
I think running time will be O(n). Since i am deleting the traversed nodes from the set of starting time.
- qasim.hasnain13 May 14, 2015startTime.erase(i);
So we are visiting each process exactly once.