algorithm - Rowspan "clean-up"算法

Question

我有一个类似于 HTML 表格的 colspan/rowspan 功能的结构:

[
 [1,4], [4,1]
 [2,2], [2,2]
 [1,1], [1,1], [1,1], [1,1]
]

就像

<tr>
  <td rowspan=4></td>
  <td colspan=4></td>
</tr>
<tr>
  <td rowspan=2 colspan=2></td>
  <td colspan=2 rowspan=2></td>
</tr>
<tr>
  <td></td>
  <td></td>
  <td></td>
  <td></td>
</tr>

----------------
|  |           |
|  |-----------|
|  |     |     |
|  |-----------|
|  |  |  |  |  |
----------------

第二行(以及第一行的第一个单元格，跨越所有 4 行)

[
 [1,3], [4,1]
 [2,1], [2,1]
 [1,1], [1,1], [1,1], [1,1]
]

和表的“拓扑”保持不变

不过像个表

[
 [1,4], [4,1]
 [2,2], [2,1]
 [2,1],
 [1,1], [1,1], [1,1], [1,1]
]

----------------
|  |           |
|  |-----------|
|  |     |     |
|  |     |-----|
|  |     |     |
|  |-----------|
|  |  |  |  |  |
----------------

不是“可折叠的”

执行此转换或保持表格原样的有效算法是什么？任何编程语言都可以。

假设结构是有效的(没有丢失单元格，表格是矩形的)如果它简化了任务

Answer 1

将单元格范围转换为坐标。

  0  1  2  3  4  5
0 ----------------
  |  |           |
1 |  |-----------|
  |  |     |     |
  |  |     |     |
  |  |     |     |
3 |  |-----------|
  |  |  |  |  |  |
4 ----------------

计算已排序的 y 坐标集(0, 1, 3, 4)。将每个坐标映射到其在集合中的索引(0:0, 1:1, 3:2, 4:3)。

计算已排序的 x 坐标集(0、1、2、3、4、5)。将每个坐标映射到它在集合中的索引(标识映射)。

  0  1  2  3  4  5
0 ----------------
  |  |           |
1 |  |-----------|
  |  |     |     |
  |  |     |     |
  |  |     |     |
2 |  |-----------|
  |  |  |  |  |  |
3 ----------------

将单元格坐标转换回范围。