Finding_Infinity's blog

Need Help in This Standard Problem of Interval Covering
By Finding_Infinity, history, 5 years ago, In English

Given an interval [L, R]. Given an array of intervals in the form of Li and Ri. How many minimum intervals required to cover the range [L, R]? Intervals can overlap with each other. L>=1 && R<=1e5 Li>=1 && Ri<=1e5 The size of the array <= 1e5

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Finding_Infinity (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think it can be done by sorting and pointers:

  1. Sort the intervals according to 'r' and if two intervals have same 'r' choose the interval having max diff of |r-l|. After that remove(ignore) all intervals having same 'r' except the one which have maximum difference of |r-l|.

  2. Now starting from any interval having r>=R which intersects R, move towards left up_to and also make a variable eg: maxL , which stores the maximum l you ever reached. If maxL becomes smaller than the current interval's l then update maxL and increase the count.

  3. Stop when you reach the desired L, and print the count.

I think this should work.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    initially , count = 1.

    Start increasing count when you've come the left of R.

    → Reply