HOME

Given a list of periods (begin-end) this algorithm will join and merge periods that have intersection.

``````

#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

typedef int DateTime;

struct Period
{
DateTime begin = 0;
DateTime end = 0;
bool operator == (const Period& other) const
{
return begin == other.begin && end == other.end;
}
bool operator < (const Period& other) const
{
//only begin is used on purpouse
return begin < other.begin;
}
};

// This algorithm build a new version of v
// v is always in a final state (no orverlapping)
{
if (v.empty())
{
v.push_back(period);
}
else
{
//it points to the period that has begin >= period.begin
auto it = lower_bound(v.begin(), v.end(), period);
const int index = it == v.end() ? -1 : it - v.begin();

if (it == v.end())
{
//The added period  is represented as { }
// 1 - ... [ { ] }
// 2 - ... [ { } ]
// 3 - ... [  ] { }

if (period.begin < v.back().end)
{
// 1 - ... [ { ] }
// 2 - ... [ { } ]

if (period.end > v.back().end)
{
// 1 - ... [ { ] }
v.back().end = period.end; //ok
}
else
{
// 2 - ... [ { } ]  or exactly the same
}
}
else
{
// 3 - ... [  ] { }
v.push_back(period); //ok
}
}
else
{
if (index > 0 && v[index - 1].end > period.begin)
{
//  ..[ { ] [ ] [ ] ...
//          ^

it = v.begin() + (index - 1);

// it now points to the previous period

//  ..[ { ] [ ] [ ] ...
//    ^
}
else
{
//  ... [ ] { [ ] [ ] ...
//            ^

//fixing the current period begin
it->begin = period.begin;
}

//finding the last period and remove
//periods in between

DateTime last = period.end > it->end ? period.end : it->end;

auto it2 = it + 1;
for (; it2 != v.end() && it2->begin <= period.end; it2++)
{
last = period.end > it2->end ? period.end : it2->end;
}

//fix end
it->end = last;

//remove periods in between
v.erase(it + 1, it2);
}
}
}

//This function is used in tests. It builds
//the period given the string representation
//For instance " [ ] " the period is 1 - 3
//             " |   " the period is 1 - 1
static void BuildVectorForTest(vector<Period>& v, const char* s)
{
DateTime begin = 0;
int i = 0;
while (s[i] != 0)
{
if (s[i] == '[')
{
//start
begin = i;
}
else if (s[i] == ']')
{
//end
}
else if (s[i] == '|')
{
//start==end
}
i++;
}
}

void Test1()
{
//[ ]
vector<Period> v;
vector<Period> v2 = { { 1, 6 },{ 7, 16 } };
assert(equal(v.begin(), v.end(), v2.begin()));
}

void Test(const char* periods[], int size)
{
vector<Period> v;
for (int i = 0; i < size - 1; i++)
{
vector<Period> v2;
BuildVectorForTest(v2, periods[i]);
}

vector<Period> v2;
BuildVectorForTest(v2, periods[size - 1]);
if (v2.size() == v.size())
{
assert(equal(v.begin(), v.end(), v2.begin()));
}
else
{
assert(false);
}
}

void Test2()
{
const char* periods[] =
{
" | ",
"   | ",
" | | " //aswer
};
Test(periods, sizeof(periods) / sizeof(periods[0]));
}

void Test3()
{
const char* periods[] =
{
" [ ]",
"     [ ]",
" [       ]",
" [       ]" //aswer
};
Test(periods, sizeof(periods) / sizeof(periods[0]));
}

void Test4()
{
const char* periods[] =
{
" [ ]",
"      |",
" [ ]  |" //aswer
};
Test(periods, sizeof(periods) / sizeof(periods[0]));
}

void Test5()
{
const char* periods[] =
{
" |    ",
"     |",
" [   ] ",
" [   ] " //asnwer
};
Test(periods, sizeof(periods) / sizeof(periods[0]));
}
void Test6()
{
const char* periods[] =
{
" [   ]             ",
"       [   ]       ",
"             [   ] ",
"   [           ]   ",
" [               ]   " //asnwer
};
Test(periods, sizeof(periods) / sizeof(periods[0]));
}

int main()
{
Test6();
Test5();
Test4();

Test1();
Test2();
Test3();

return 0;
}
``````