1,000+ ASIC Interview Questions: SystemVerilog, UVM & RTL

DescriptionQ218

Page ↗

Q218FWASIC interview problem

Merge inclusive overlapping intervals

TechniquesSystemVerilogIntervalsSortingSweep

DifficultyMedium

TopicArrays

LanguageSystemVerilog

Requirements4 checkpoints

Problem

Given a queue of inclusive [start, end] intervals, merge every overlap and return the merged intervals sorted by start.

Type declarationSystemVerilog

typedef struct {
  int unsigned start_val;
  int unsigned end_val;
} interval_t;

function automatic interval_t[$]
merge_intervals(interval_t intervals[$]);

Example input and output

Use this case to check your interpretation

Input

intervals = [[1,2], [2,4], [6,7], [8,9]]

Output

[[1,4], [6,7], [8,9]]

Explanation

Inclusive ranges sharing endpoint 2 merge, while [6,7] and [8,9] remain separate because adjacency alone is not overlap.

Requirements (4)

Assume every input interval satisfies start_val <= end_val.
Merge intervals that share an endpoint, such as [1,2] and [2,4].
Do not merge merely adjacent integer ranges such as [1,2] and [3,4].
Return an empty queue for empty input.