Help, please!
Hello!
I got task for some project to do, but I really don't know how to start. If someone can help me, I would be grateful. :)
___________________________
You are given N open intervals on a line (the intervals do not include their endpoints). Your task is to write a program which finds the largest number of intervals that can be chosen so they don't intersect.
INPUT:
The first line of the standard input contains a number N (0<N<=5000), the number of intervals. The next N lines contain two integers li and ri (-10000< li < di <10000) which represent the left and right ends of the interval (1<=i<=N).
OUTPUT:
To the standard output in one line write the number of intervals which can be chosen so that they do not intersect.
Input:
4
-1 1
0 5
2 3
5 9
Output:
3
P.S. The program is required to implement function, which checks whether two intervals have a common point: bool check (int p1, int k1, int p2, int k2).I am suffering with this for a long time and I can not resolve it, the task should be solved using the iostream library.
[/b]
I got task for some project to do, but I really don't know how to start. If someone can help me, I would be grateful. :)
___________________________
You are given N open intervals on a line (the intervals do not include their endpoints). Your task is to write a program which finds the largest number of intervals that can be chosen so they don't intersect.
INPUT:
The first line of the standard input contains a number N (0<N<=5000), the number of intervals. The next N lines contain two integers li and ri (-10000< li < di <10000) which represent the left and right ends of the interval (1<=i<=N).
OUTPUT:
To the standard output in one line write the number of intervals which can be chosen so that they do not intersect.
Input:
4
-1 1
0 5
2 3
5 9
Output:
3
P.S. The program is required to implement function, which checks whether two intervals have a common point: bool check (int p1, int k1, int p2, int k2).I am suffering with this for a long time and I can not resolve it, the task should be solved using the iostream library.
[/b]
I expect that you figured out the brute-force algorithm at least.
¿What is giving you trouble?
[]{}
{}[]
[{}]
{[]}
[{]}
{[}]
You could simplify if you force that the first interval will be the more 'left' (the one with the smaller start). So you actually have to look up for:
[]{}
[{}]
[{]}
where only the first one does not intersect, and that's an easy check (it ends before the other starts).
¿What is giving you trouble?
bool check(int beg1, int end1, int beg2, int end2); Assumming beg<end these are the patterns that can show up:[]{}
{}[]
[{}]
{[]}
[{]}
{[}]
You could simplify if you force that the first interval will be the more 'left' (the one with the smaller start). So you actually have to look up for:
[]{}
[{}]
[{]}
where only the first one does not intersect, and that's an easy check (it ends before the other starts).
I didn't do anything. I don't realize this task and I don't know how to start, I don't know what I need to do in this task, or anything. I need the whole code. If anyone can solve this, please help me, it's an emergency.
Hmm sounds like homework. If you say its an "emergency", it's likely due soon. Why did you procrastinate so much? And why would we post the whole code for you...? It's not our work, and we gain nothing from this. This is your opportunity to learn what you're supposed to.
You don't need me to send the whole code, but can you at least explain the task, or write pseudocode. And I will do it alone. :)
Topic archived. No new replies allowed.