Data Visualization: Keep line labels apart

Direct labels at the ends of lines collide when the lines end close together. Push labels apart so that neighbours are at least a minimum gap away.

What to build

A program that adjusts label positions to remove overlaps.

Requirements

  • Process the labels in order of position (smallest first, input order on ties). The first keeps its position; each next one moves to the larger of its own position and the previous label's new position plus the gap.
  • Print NAME Y for each label in input order, with Y in :g format.

Input

Line 1: the gap. Line 2: n. Then n lines NAME Y.

Output

n lines.

Constraints

1 ≤ n ≤ 50; 0 < gap ≤ 100; positions are between −10⁴ and 10⁴.

Example

Input:

2
3
A 10
B 11
C 20

Output:

A 10
B 12
C 20

Why it works

Working upwards from the lowest label and only ever moving labels in one direction guarantees every pair of neighbours ends at least the gap apart, while labels that had room never move.

Examples

Example 1 · Input
2
3
A 10
B 11
C 20
Expected output
A 10
B 12
C 20
Example 2 · Input
1
1
X 5
Expected output
X 5

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Sort the labels by position with a stable sort, keeping their input order on ties.

Hint 2

Each label's new position is the larger of its own position and the previous label's position plus the gap.

Hint 3

Print the results in the original input order.

Solution

Show one correct solution (try it yourself first)
gap = float(input())
n = int(input())
labels = []
for _ in range(n):
    name, y = input().split()
    labels.append([name, float(y)])
prev = None
for label in sorted(labels, key=lambda l: l[1]):
    if prev is not None:
        label[1] = max(label[1], prev + gap)
    prev = label[1]
for name, y in labels:
    print(name, f"{y:g}")

Lesson: Annotation and small multiples →