Covering segments by points

Question

I did search and looked at these below links but it didn't help .

1. Point covering problem
2. Segments poked (covered) with points - any tricky test cases?
3. Need effective greedy for covering a line segment

Problem Description:

 You are given a set of segments on a line and your goal is to mark as
 few points on a line as possible so that each segment contains at least
 one marked point

Task.

  Given a set of n segments {[a0,b0],[a1,b1]....[an-1,bn-1]} with integer
  coordinates on a line, find the minimum number 'm' of points such that 
  each segment contains at least one point .That is,  find a set of 
  integers X of the minimum size such that for any segment [ai,bi] there 
  is a point x belongs X such that ai <= x <= bi

Output Description:

  Output the minimum number m of points on the first line and the integer 
coordinates of m points (separated by spaces) on the second line

Sample Input - I

3
1 3
2 5
3 6

Output - I

1  
3

Sample Input - II

4
4 7
1 3
2 5
5 6

Output - II

2   
3 6 

I didn't understand the question itself. I need the explanation, on how to solve this above problem, but i don't want the code. Examples would be greatly helpful

Answer 1

Maybe this formulation of the problem will be easier to understand. You have n people who can each tolerate a different range of temperatures [ai, bi]. You want to find the minimum number of rooms to make them all happy, i.e. you can set each room to a certain temperature so that each person can find a room within his/her temperature range.

As for how to solve the problem, you said you didn't want code, so I'll just roughly describe an approach. Think about the coldest room you have. If making it one degree warmer won't cause anyone to no longer be able to tolerate that room, you might as well make the increase, since that can only allow more people to use that room. So the first temperature you should set is the warmest one that the most cold-loving person can still tolerate. In other words, it should be the smallest of the bi. Now this room will satisfy some subset of your people, so you can remove them from consideration. Then repeat the process on the remaining people.

Now, to implement this efficiently, you might not want to literally do what I said above. I suggest sorting the people according to bi first, and for the ith person, try to use an existing room to satisfy them. If you can't, try to create a new one with the highest temperature possible to satisfy them, which is bi.

Answer 2

Yes the description is pretty vague and the only meaning that makes sense to me is this:

1. You got some line

2. Segment on a line is defined by l,r

   Where one parameter is distance from start of line and second is the segments length. Which one is which is hard to tell as the letters are not very usual for such description. My bet is:

   • l length of segment
   • r distance of (start?) of segment from start of line

   

3. You want to find min set of points

   So that each segment has at least one point in it. That mean for 2 overlapped segments you need just one point ...

Surely there are more option how to solve this, the obvious is genere & test with some heuristics like genere combinations only for segments that are overlapped more then once. So I would attack this task in this manner (using assumed terminology from #2):

1. sort segments by r

2. add number of overlaps to your segment set data

   so the segment will be { r,l,n } and set the n=0 for all segments for now.

3. scan segments for overlaps

   something like

   for (i=0;i<segments;i++) // loop all segments
    for (j=i+1;j<segments;j++) // loop all latter segments until they are still overlapped
     if ( segment[i] and segment [j] are overlapped )
      {
      segment[i].n++; // update overlap counters
      segment[j].n++;
      }
     else break;
   

   Now if the r-sorted segments are overlapped then

   segment[i].r             <=segment[j].r
   segment[i].r+segment[i].l>=segment[j].r
   

4. scan segments handling non overlapped segments

   for each segment such that segment[i].n==0 add to the solution point list its point (middle) defined by distance from start of line.

   points.add(segment[i].r+0.5*segment[i].l);
   

   And after that remove segment from the list (or tag it as used or what ever you do for speed boost...).

5. scan segments that are overlapped just once

   So if segment[i].n==1 then you need to determine if it is overlapped with i-1 or i+1. So add the mid point of the overlap to the solution points and remove i segment from list. Then decrement the n of the overlapped segment (i+1 or i-1)` and if zero remove it too.

   points.add(0.5*( segment[j].r + min(segment[i].r+segment[i].l , segment[j].r+segment[j].l )));
   

   Loop this whole scanning until there is no new point added to the solution.

6. now you got only multiple overlaps left

   From this point I will be a bit vague for 2 reasons:

   1. I do not have this tested and I d not have any test data to validate not to mention I am lazy.
   2. This smells like assignment so there is some work/fun left for you.

   From start I would scann all segments and remove all of them which got any point from the solution inside. This step you should perform after any changes in the solution.

   Now you can experiment with generating combination of points for each overlapped group of segments and remember the minimal number of points covering all segments in group. (simply by brute force).

   There are more heuristics possible like handling all twice overlapped segments (in similar manner as the single overlaps) but in the end you will have to do brute force on the rest of data ...

[edit1] as you added new info

The r,l means distance of left and right from the start of line. So if you want to convert between the other formulation { r',l' } and (l<=r) then

l=r`
r=r`+l`

and back

r`=l
l`=r-l`

Sorry too lazy to rewrite the whole thing ...

Answer 3

Here is the working solution in C, please refer to it partially and try to fix your code before reading the whole. Happy coding :) Spoiler alert

#include <stdio.h>
#include <stdlib.h>

int cmp_func(const void *ptr_a, const void *ptr_b)
{
    const long *a = *(double **)ptr_a;
    const long *b = *(double **)ptr_b;

    if (a[1] == b[1])
        return a[0] - b[0];

    return a[1] - b[1];
}

int main()
{
    int i, j, n, num_val;
    long **arr;
    scanf("%d", &n);
    long values[n];
    arr = malloc(n * sizeof(long *));

    for (i = 0; i < n; ++i) {
        *(arr + i) = malloc(2 * sizeof(long));
        scanf("%ld %ld", &arr[i][0], &arr[i][1]);
    }

    qsort(arr, n, sizeof(long *), cmp_func);

    i = j = 0;
    num_val = 0;

    while (i < n) {
        int skip = 0;
        values[num_val] = arr[i][1];

        for (j = i + 1; j < n; ++j) {
            int condition;
            condition = arr[i][1] <= arr[j][1] ? arr[j][0] <= arr[i][1] : 0;

            if (condition) {
                skip++;
            } else {
                break;
            }
        }

        num_val++;
        i += skip + 1;
    }

    printf("%d\n", num_val);

    for (int k = 0; k < num_val; ++k) {
        printf("%ld ", values[k]);
    }

    free(arr);
    return 0;
}

Answer 4

Here's the working code in C++ for anyone searching :)

#include <bits/stdc++.h>
#define ll long long 
#define double long double
#define vi vector<int>
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define mp make_pair
using namespace std;

bool cmp(const pair<ll,ll> &a, const pair<ll,ll> &b)
{
    return (a.second < b.second);
}
vector<ll> MinSig(vector<pair<ll,ll>>&vec)
{ 
    vector<ll> points;
    for(int x=0;x<vec.size()-1;)
    {
        bool found=false;
        points.pb(vec[x].ss);
        for(int y=x+1;y<vec.size();y++)
        {
            if(vec[y].ff>vec[x].ss)
            {
                x=y;
                found=true;
                break;
            }
          
        }
        if(!found)
        break;

    }
    return points;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    vector<pair<ll,ll>>v;
    for(int x=0;x<n;x++)
    {
        ll temp1,temp2;
        cin>>temp1>>temp2;
        v.pb(mp(temp1,temp2));
    }
    sort(v.begin(),v.end(),cmp);
    vector<ll>res=MinSig(v);
    cout<<res.size()<<endl;
    for(auto it:res)
    cout<<it<<" ";
}