Tripos 2022 Paper 1 Question 2 — Worked Solution

Question: Represent sets of integers as lists of intervals.

type intset = (int * int) list

An interval list is in standard form if it is an ascending sequence of non-empty intervals that cannot be merged. Example: {1,2,3,9,10,11,12} is [(1,3);(9,12)].

(a)(i) Test standard form [4 marks]

let rec is_standard = function
  | [] -> true
  | [(a, b)] -> a <= b
  | (a1, b1) :: (a2, b2) :: rest ->
      a1 <= b1 && b1 + 1 < a2 && is_standard ((a2, b2) :: rest)

Explanation: An interval list is in standard form if three conditions hold:

1. Every interval is non-empty: for each (a, b), we must have a ≤ b.
2. Intervals are ascending: the start of each interval is greater than the end of the previous interval plus 1 — if b1 + 1 ≥ a2, the intervals (a1, b1) and (a2, b2) overlap or touch and should be merged.
3. No adjacent intervals can be merged: this is exactly b1 + 1 < a2.

We check these conditions recursively. The singleton case only checks a ≤ b. For two or more intervals, we verify the first interval is non-empty (a1 ≤ b1), that it cannot merge with the next (b1 + 1 < a2), and recursively check the rest. Time complexity: O(n) where n is the number of intervals.

(a)(ii) Add interval to standard form [4 marks]

let rec add_interval (a, b) = function
  | [] -> [(a, b)]
  | (a', b') :: rest ->
      if b + 1 < a' then (a, b) :: (a', b') :: rest
      else if b' + 1 < a then (a', b') :: add_interval (a, b) rest
      else
        let a'' = min a a' in
        let b'' = max b b' in
        add_interval (a'', b'') rest

Explanation: We insert (a, b) while maintaining standard form. There are three cases when comparing with the head interval (a', b'):

1. No overlap, new interval before: If b + 1 < a', the new interval is completely before the head — prepend it and we’re done.

2. No overlap, new interval after: If b' + 1 < a, the head interval is completely before the new one — keep the head and recursively try to insert into the rest.

3. Overlap or touch: The intervals can be merged. We compute the merged interval (min a a', max b b') and recursively insert this merged interval into rest. This may trigger further merges with subsequent intervals.

This is O(n) time in the worst case (when the new interval merges with all existing intervals, reducing the list to a single interval).

(a)(iii) Convert to standard form [2 marks]

let standardize intset =
  List.fold_left (fun acc iv -> add_interval iv acc) [] intset

Explanation: We start with an empty list (trivially in standard form) and repeatedly add each interval using add_interval. Since add_interval maintains standard form, the final result is in standard form. This is O(n^2) worst-case if each addition triggers a cascade of merges, but typically much faster. This is equivalent to List.fold_left — the OCaml standard library function.

(a)(iv) Equality test [2 marks]

let equal s1 s2 =
  let s1' = standardize s1 in
  let s2' = standardize s2 in
  s1' = s2'

Explanation: Two interval lists represent the same set if their standard forms are identical (element-wise equal as lists of pairs). We standardise both and use polymorphic equality = to compare the resulting lists. Since standard form is a canonical representation, this correctly determines set equality. The time complexity is dominated by the standardisation step: O(n^2) worst-case where n is the number of intervals. We could also write it without standardising both by doing a single pass comparison if both inputs are known to be in standard form.

(b) Intersection of integer sets [8 marks]

Write inter : intset -> intset -> intset assuming both arguments are in standard form.

let rec inter s1 s2 =
  match s1, s2 with
  | [], _ -> []
  | _, [] -> []
  | (a1, b1) :: rest1, (a2, b2) :: rest2 ->
      if b1 < a2 then
        inter rest1 s2
      else if b2 < a1 then
        inter s1 rest2
      else
        let a = max a1 a2 in
        let b = min b1 b2 in
        (a, b) :: inter
          (if b1 = b then rest1
           else (b + 1, b1) :: rest1)
          (if b2 = b then rest2
           else (b + 1, b2) :: rest2)

Explanation: We process both sorted interval lists simultaneously, similar to merging two sorted lists. For the head intervals (a1, b1) and (a2, b2):

1. No overlap (first entirely before second): If b1 < a2, the first interval cannot intersect with the second or any later interval (since s2 is ascending). Discard the first interval and continue.

2. No overlap (second entirely before first): If b2 < a1, discard the second interval.

3. Overlap: The intersection is (max a1 a2, min b1 b2). We output this interval. Then we need to handle the “leftover” parts of the original intervals that extend beyond the intersection:

   • If b1 > b (the first interval extends beyond the intersection), we keep (b + 1, b1) and prepend it to rest1. Otherwise we move to rest1.
   • Similarly for the second interval: if b2 > b, keep (b + 1, b2) and prepend it to rest2.

This processes each interval at most once. The time complexity is O(n1 + n2) where n1 and n2 are the numbers of intervals in s1 and s2 respectively. The result is guaranteed to be in standard form (ascending, non-empty, non-mergeable) because the intersection of intervals inherits these properties.