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

Автор gXa, история, 5 лет назад, По-английски

A list of strings of lowercase English alphabets is given.

It is followed by a list of operations, where each operation is denoted by

(a, b, c): append character c to all elements in the range a to b

c can be of three types (#,$,%), and if c is already appended to an element, adding again won't affect.

We need to find minimum number of operations required actually to get the final output.

Note: All operations must be done in the given order. We can decide to skip it or not.

Given list of strings: a, b, c, d

Operations:

1. 1 2 $

2. 1 4 $

Output: 1

It is because 2 would bring the final output itself.

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

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

It can be solved with scanline. Push back evry segment as {L, -1, char}, {R, 1, char}, sort it. You have a set of current symbols in current point. Iterate over all points, if second element is -1, you opening segment, if 1 — closing. If new point with second value with -1 appends char to set of symbols at current point, just insert it to set, and add 1 to answer.