mahmutdemir
BAN USERWritten in C++ using heap data structure.
struct Entry{
int start;
int end;
int flow;
};
struct CompStart
{
bool operator()(const Entry& a, const Entry& b)
{
return a.start > b.start;
}
};
struct CompEnd
{
bool operator()(const Entry& a, const Entry& b)
{
return a.end > b.end;
}
};
int findMaxFlow(vector<Entry> entries)
{
vector<Entry> entriesStart(entries);
vector<Entry> entriesEnd(entries);
make_heap(entriesStart.begin(), entriesStart.end(), CompStart());
make_heap(entriesEnd.begin(), entriesEnd.end(), CompEnd());
int runningFlow = 0;
int maxFlow = 0;
int time = 0;
while(!entriesStart.empty())
{
time = entriesStart.front().start;
runningFlow += entriesStart.front().flow;
pop_heap(entriesStart.begin(), entriesStart.end(), CompStart());
entriesStart.pop_back();
make_heap(entriesStart.begin(), entriesStart.end(), CompStart());
while(!entriesEnd.empty() && time >= entriesEnd.front().end)
{
time = entriesEnd.front().end;
runningFlow -= entriesEnd.front().flow;
pop_heap(entriesEnd.begin(), entriesEnd.end(), CompEnd());
entriesEnd.pop_back();
make_heap(entriesEnd.begin(), entriesEnd.end(), CompEnd());
if(runningFlow > maxFlow)
maxFlow = runningFlow;
}
if(runningFlow > maxFlow)
maxFlow = runningFlow;
}
return maxFlow;
}
int main()
{
vector< Entry > entries = {{0,10,100}, {10,15,300}, {16,20,400}, {5,15,200}};
cout << findMaxFlow(entries) ;
return 0;
}
Recursive printout of k-combination of numbers 1 to n
void printComb(int start, int end, int k, vector<int>& line)
{
if(k == 0)
{
for(int j = 0; j < line.size(); j++)
cout << line[j] << " ";
cout << endl;
}
else
{
for(int i = start; i <= end; i++)
{
line.push_back(i);
printComb(i+1, end, k-1, line);
line.pop_back();
}
}
}
RepRaimeCarrillo, Area Sales Manager at 247quickbookshelp
Hi, I am Raime from Tampa USA . I work as an Local account executive employee. I work in many fields ...
RepSuzaneVenable, Applications Developer at 247quickbookshelp
I am an employment manager typically in charge of planning the hiring processes, setting guidelines and timelines, and establishing budgets ...
RepDavlinaSmith, abc at ADP
I am a current residential landlord with 5 years’ experience looking to expand into commercial property management.Former florist by ...
- mahmutdemir January 31, 2016