Counting maximum number of overlapping intervals

[antoniu200]

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.

Restrictions and clarifications

1 ≤ n ≤ 100,000;
-1,000,000,000 ≤ A<i> < B<i> ≤ 1,000,000,000;
- memory limit: 4 MB / 2 MB;
- time limit: 0.1 seconds.


Example

nrmaxinterv.in

5
1 4
0 3
8 12
5 9
5 11

nrmaxinterv.out

3

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.

This is my code

#include <bits/stdc++.h>
using namespace 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 ++;
            else break;
        }
        mx=max(over,mx);
    }
    out << mx;
}

[salem c]

nrmaxinterv.in

5
1 4
0 3
8 12
5 9
5 11

nrmaxinterv.out

3

Do you have more examples to work with?

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);

[antoniu200]

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.

[Mapler]

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.

   +1   -1
    ....
+1  .  .  -1
  ...  ...
  .      .
------------->
  3 5  8 10

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.

[antoniu200]

This might be helpful, I will give this a try. Thanks! I'll report back with the results once I have some time to implement it.