Counting maximum number of overlapping intervals

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, B], 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 and B 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 < B ≤ 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

 ``123456789101112131415161718192021222324252627282930313233343536373839`` ``````#include 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; }``````
Last edited on
 ``123456789101112`` ``````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);

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.
Last edited on
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:

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