Redaksiya

Sort the segments by their right endpoints. Start by selecting the first segment, then remove any segments that intersect with it. Next, choose the leftmost remaining segment and remove any segments that intersect with this one. By following this greedy approach, we maximize the number of non-overlapping segments selected.

Algorithm implementation

Declare a class segment to represent an interval $[s t a r t; f in)$ .

class segment
{
public:
  int start, fin;
  segment(int start, int fin) : start(start), fin(fin) {}
};

Store the set of input intervals in a vector $v$ .

vector<segment> v;

The function f is a comparator for sorting intervals in ascending order by their right endpoint.

int f(segment a, segment b)
{
  return a.fin < b.fin;
}

The main part of the program. Read the input data.

scanf("%d", &n);
while (n--)
{
  scanf("%d %d", &a, &b);
  v.push_back(segment(a, b));
}

Sort the segments.

sort(v.begin(), v.end(), f);

Let the current interval being processed be denoted as $c u r$ . Start the algorithm with the zeroth interval by setting $c u r = 0$ . Initialize a counter $res$ , to keep track of the number of selected intervals. Since the zeroth interval is initially selected, set $res = 1$ .

cur = 0; res = 1;

Iterate through the intervals, starting from $i = 1$ .

for (i = 1; i < v.size(); i++)
{

For each interval, look for one whose start is not less than the end of the current $c u r$ . When such an interval is found, select it and update $c u r$ to this new interval.

  if (v[i].start >= v[cur].fin)
  {
    cur = i;
    res++;
  }
}

Print the maximum number of non-overlapping intervals.

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

Java implementation

import java.util.*;

class Segment
{
  int start, fin;

  public Segment(int start, int fin) 
  {
    this.start = start;
    this.fin = fin;
  }
}

public class Main 
{
  public static class MyFun implements Comparator<Segment> 
  {
    public int compare(Segment a, Segment b)
    {
      return a.fin - b.fin;
    }
  }
	
  public static void main(String[] args) 
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    ArrayList<Segment> seg = new ArrayList<Segment>();    

    for (int i = 0; i < n; i++)
    {
      int a = con.nextInt();
      int b = con.nextInt();
      seg.add(new Segment(a,b));  
    }
      
    Collections.sort(seg, new MyFun());    
    
    int cur = 0, res = 1;
    for (int i = 1; i < seg.size(); i++)
    {
      if (seg.get(i).start >= seg.get(cur).fin)
      {
        cur = i;
        res++;
      }
    }
    
    System.out.println(res);
    con.close();
  }
}