lab1.cpp

#include <iostream>
#include <algorithm>
using namespace std;

void findMinimumPointSet(int* points, int numPoints, pair<int, int>* intervals, int numIntervals, int* result, int& resultSize) {
    sort(intervals, intervals + numIntervals, [](const pair<int, int>& i1, const pair<int, int>& i2){
        return i1.second < i2.second;});
    int curr=-1;
    resultSize=0; 
    for(int i=0;i<numIntervals;i++) {
        if (curr<intervals[i].first) {
            int left = 0, right = numPoints;
            while(left < right) {
                int mid = left + (right - left) / 2;
                if(points[mid] <= intervals[i].second) left = mid + 1;
                else right = mid;
            }
            left--;
            if (left >= 0 && points[left] >= intervals[i].first) {
                curr = points[left];
                result[resultSize++] = curr;
            }
        }
    }
}


int main() {
    int n;
    cout<<"No. of points: ";
    cin>>n;
    cout<<"Points: ";
    int points[n];
    for(int i=0;i<n;i++) {
        cin>>points[i];
    }
    cout<<"No. of intervals: ";
    int m;
    cin>>m;
    cout<<"Intervals: ";
    pair<int, int> intervals[m];
    for(int i=0;i<m;i++) {
        cin>>intervals[i].first>>intervals[i].second;
    }
    sort(points,points+n);
    int result[n];
    int resultSize=0;
    findMinimumPointSet(points,n, intervals,m,result,resultSize);
    
    cout << "Minimum set of points: ";
    for (int i=0;i<resultSize;i++)  {
        cout << result[i] << " ";
    }
    cout << '\n';
    
    return 0;
}
/*n: Number of points.
points[]: Array of points, sorted in ascending order.
m: Number of intervals.
intervals[]: Array of intervals, where each interval is represented as a pair of integers (first, second), denoting the start and end of the interval.*/

/*
The intervals are sorted by their end points (intervals[i].second). Sorting by end points allows the algorithm to greedily select the smallest point that covers the largest number of intervals.
*/

/*
The main logic for selecting the minimum set of points that cover all intervals is implemented here.
curr: Tracks the current point that was last selected to cover an interval.
For each interval, if the current point (curr) does not cover the interval, the algorithm finds the largest point (using binary search) that is within the current interval and selects that point.
This point is added to the result[] array, and resultSize keeps track of how many points have been selected.
*/