Rich Text to HTML

A rich-text editor stores your document as plain text plus a list of formatting ranges: "characters 0 through 4 are bold", "characters 2 through 6 are italic". To render or save that document, you serialize it to HTML. The catch is that ranges overlap freely — the user can bold a word and italicize the second half of it — but HTML tags must be properly nested. You cannot emit <b>The <i>quick</b> brown</i>; a browser will silently repair it and your round-trip breaks. Your job is to turn an arbitrary set of overlapping ranges into a single, valid, deterministic HTML string.

Implement richTextToHtml(doc).

Signature

// doc: {
//   text: string,
//   ranges: Array<{ start: number, end: number, tag: string }>
// }
//   Each range styles the HALF-OPEN interval [start, end) with `tag`
//   (a bare tag name like 'b', 'i', 'u'). [start, end) includes the
//   character at `start` and excludes the character at `end`. Ranges may
//   overlap, nest, or share bounds arbitrarily, in any array order.
//
// returns: string
//   HTML in which every range's styling is applied to exactly its
//   characters, all tags are WELL-NESTED, and the text's special
//   characters (&, <, >) are escaped.
function richTextToHtml(doc): string;

Examples

// Two non-overlapping ranges, each its own tag pair. Half-open intervals
// mean [0,2) covers "ab" and [2,4) covers "cd" — they do not share a char.
richTextToHtml({
  text: 'abcd',
  ranges: [
    { start: 0, end: 2, tag: 'b' },
    { start: 2, end: 4, tag: 'i' },
  ],
});
// → "<b>ab</b><i>cd</i>"

// Two OVERLAPPING ranges. bold = [0,4) "abcd", italic = [2,6) "cdef".
// The overlap forces a split at every boundary (0, 2, 4, 6) into three
// segments. In the middle segment both tags are active and must nest;
// bold opened first, so bold is the outer tag.
richTextToHtml({
  text: 'abcdef',
  ranges: [
    { start: 0, end: 4, tag: 'b' },
    { start: 2, end: 6, tag: 'i' },
  ],
});
// → "<b>ab</b><b><i>cd</i></b><i>ef</i>"
//    |- b only -||--  b + i  --||- i only -|

Notes

• Intervals are half-open: [start, end). The character at start is included; the character at end is excluded. So [0, 3) and [3, 6) are adjacent siblings, not overlapping — they share no character. An off-by-one here is the most common bug.
• Where ranges overlap, split into segments at every boundary. Collect all start and end offsets (plus 0 and text.length). Consecutive offsets bound a segment over which the set of active tags is constant.
• Within a segment, tags are emitted in a canonical, documented order. Sort the active tags by their range's start ascending (the range that opened earliest is the outermost tag); break ties by end descending (the wider range is more enclosing, so it goes outer); break remaining ties alphabetically by tag name; then by original array index. This makes the output deterministic — the same input always produces byte-for-byte the same string, regardless of the order ranges appear in the input array.
• Re-open tags across segment boundaries. A range spanning two segments closes at the first segment's end and re-opens at the next segment's start, so each segment is independently well-nested. <b>ab</b><b><i>cd</i></b> re-opens <b> rather than leaving it dangling.
• Escape &, <, and > in the text (to &, <, >) so literal characters in the document never become markup. Tag names you emit are trusted and not escaped.
• Valid nesting is guaranteed by construction. Because every segment opens and closes its full active-tag set inside that segment, the output can never interleave improperly.
• Don't worry about tag attributes (links with href), block-level tags, minimizing tag churn across segments, or validating that tag is a real HTML element — see Going further in the solution.