All problems

Lighthouse Sightings

Medium · heap

A stretch of coast has several lighthouses, numbered from 0. logs[j] is the logbook of lighthouse j: the times (in seconds) at which it spotted a ship, already written in order from earliest to latest. A lighthouse that never saw a ship has an empty logbook, and a lighthouse can note the same time more than once.

The harbour master wants to know which lighthouse reported each of the first limit sightings, once all the logbooks are read together in time order. When two sightings happen at the same time, the one from the lighthouse with the smaller number comes first, and two equal times in one logbook keep their order.

Return the lighthouse number of each of those sightings, in order. If there are fewer than limit sightings in total, return the lighthouse number of every one of them.

Examples

Example 1

Input: logs = [[1, 4, 9], [2, 3], [4, 5]], limit = 5

Output: [0, 1, 1, 0, 2]

In time order the sightings are 1 (lighthouse 0), 2 and 3 (lighthouse 1), then two at time 4: lighthouse 0 first, then lighthouse 2.

Example 2

Input: logs = [[], [7]], limit = 3

Output: [1]

There is only one sighting in total, so only one number is returned.

Example 3

Input: logs = [[5, 5], [5]], limit = 2

Output: [0, 0]

All three sightings are at time 5. Lighthouse 0 wins the tie for both of the first two places.

Constraints