1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Help!

Discussion in 'C++' started by eveline, Jan 21, 2012.

  1. eveline

    eveline New Member

    Joined:
    Jan 21, 2012
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    Hello!

    I'm new here, but for a long time following this forum. 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. 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.

    ___________________________

    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 beg1, int end1, int beg2, int end2).I am suffering with this for a long time and I can not resolve it, the task should be solved using the iostream library.
     
  2. hobbyist

    hobbyist New Member

    Joined:
    Jan 7, 2012
    Messages:
    141
    Likes Received:
    0
    Trophy Points:
    0
    c++ is a bit advanced for me, but I *think* you can use a vector

    declare a 2d vector
    Code:
    std::vector<std::vector<int> > intervals;
    add some data
    Code:
    loop(while input is stored) {
       intervals.push_back(std::vector<int>(2)); // prepare a set of end pts
       // request end pt 1 and end pt 2
       std::cin >> intervals[loop_counter][0] // end pt 1
       std::cin >> intervals[loop_counter][1] // end pt 2
    }

    I *think* the function would want to check intervals[0][0], intervals[0][1] against the other sets in the vector, so use a loop starting at index pos 1
    Code:
    for(int i=1; i < intervals.size(); ++i) {
       if(check(intervals[0][0], intervals[0][1], intervals[i][0], intervals[i][1]) == false)
          ++count;
    }
    oops; forgot the function
    Code:
    bool check(int s1, int e1, int s2, int e2) {
       return (s2 >= s1 && e2 <= e1);
    }

    maybe something like that.
    HTH
     

Share This Page