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:
Requirement
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).
Input data
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.
Output data
The output file nrmaxinterv.out contains on the first line the natural number NR, representing the maximum number of overlapping intervals.
One might think this is homework, it is not, the exercise is way above the curriculum, at least where I live. I am a stundent wanting to learn more, so please explain thoroughly any algorithm.
#include <bits/stdc++.h>
usingnamespace std;
ifstream in("nrmaxinterv.in");
ofstream out("nrmaxinterv.out");
struct type
{
long limitL, limitR;
} v[100001];
bool compareL (type lhs, type rhs)
{
return (lhs.limitL < rhs.limitL);
};
bool compareR (type lhs, type rhs)
{
return (lhs.limitR < rhs.limitR);
};
int main()
{
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)
over ++;
elsebreak;
}
mx=max(over,mx);
}
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.