4786. Segments

 

Segments are given on a line. Determine the maximum number of segments that can be selected such that no two of them intersect. All segments are open.

 

Input. The first line contains the number of segments n (1 ≤ n ≤ 105). Each of the next n lines contains two integers, li and ri (1 ≤ li < ri ≤ 109), representing the starting and ending points of the i-th segment.

 

Output. Print the maximum number of non-intersecting segments.

 

Sample input 1

Sample output 1

5

1 4

3 8

7 8

2 5

4 6

3

 

 

Sample input 2

Sample output 2

4

1 3

2 6

1 8

2 5

1

 

 

SOLUTION

greedy

 

Algorithm analysis

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 [start; fin).

 

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 cur. Start the algorithm with the zeroth interval by setting cur = 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 cur. When such an interval is found, select it and update cur 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();

  }

}