Hi! So, I've been working on a problem from a site with C++ exercises, but I can't seem to get it to give me 100p (out of 100). The requirement sounds like this:
Consider the integer intervals [A<i>, B<i>], 1 ≤ i ≤ n. Determine the maximum number of overlapping intervals (intervals that have at least one common value).
The input file nrmaxinterv.in contains on the first line a natural number n. The following n lines describe the n intervals, one line per line. For each interval i the limits A<i> and B<i> are specified.
The output file nrmaxinterv.out contains on the first line the natural number NR, representing the maximum number of overlapping intervals.
long limitL, limitR;
bool compareL (type lhs, type rhs)
return (lhs.limitL < rhs.limitL);
bool compareR (type lhs, type rhs)
return (lhs.limitR < rhs.limitR);
long n, i, over=0,mx=0;
in >> n;
for (i = 1; i <= n; i++)
in >> v[i].limitL >> v[i].limitR;
sort (v + 1, v + n + 1, compareL);
sort (v + 1, v + n + 1, compareR);
for (i = 1; i < n; i++)
over = 1;
for (long j=i+1;j<=n;j++)
if (v[i].limitR >= v[j].limitL)
out << mx;
Because I count 4
1 4 with 0 3
8 12 with 5 9
8 12 with 5 11
5 9 with 5 11
Before you write ANY code, you need to understand fully how to work out the answer on paper. The code is just a machine representation of that understanding. You don't just write something and then wonder why it didn't work.
> sort (v + 1, v + n + 1, compareL);
This has NO effect on the result, because you then do sort (v + 1, v + n + 1, compareR);
Sorry, but that's the only example. And the second sort actually helps, because it then sorts the intervals (if needed) by the right-hand limit. And so, if you have 5 9 and 5 11, instead of showing up as 5 11 and 5 9, it will show up as 5 9, 5 11. And the problem says maximum number of overlapping intervals, not how many of them are overlapping.
Here goes my attempt of explaining: 5 9 overlaps with 5 11, 8 12 - 3 intervals; 0 3 overlaps with 1 4 - 2 intervals. So, ergo, the maximum of overlapping intervals is 3.
Like the person above said, you can benefit from drawing out the problem first before coding. It helps to get a picture of what should be going on, especially when the solution to your problem isn't immediately obvious. Anyway, I have a solution in mind that I'll try to draw here:
Let's start with a simple example.
We have 2 bounds (3,8) and (5,10). We can plot this out so that at the start of a bound, you add 1, and at the end of a bound, you subtract one.
So visually we can see where the bounds overlap. The maximum point of the graph represents the point of most overlaps. It becomes clear that there are 4 points that we care about, and those are the start and end points of the bounds. We need 2 variables for every bound.
I'll let you figure out the implementation. This is an example of modelling a solution to a problem before writing code.