Блог пользователя Finding_Infinity

Need Help in This Standard Problem of Interval Covering
Автор Finding_Infinity, история, 7 лет назад, По-английски

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

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить