XY平面上のある条件の格子点の数を求めたい

Question

以下の問いを考えるときの方針をアドバイスいただきたいです。

XY平面上の(0, 0), (n, 0), (0, m), (n, m) に囲まれる領域およびその線上の格子点を考えます。

領域内にX軸に平行な線分がランダムな長さでランダムにあります。
x = k にかかる線分の数cを数えたときにc >= qとなる線分（点の場合は[p, p]）の集合を出力したいです。

言葉だけですと伝わりにくいと思いますので画像を参考になさってみてください。

簡単に思いついたのは以下の流れです。

・結果配列を用意

・n = k のときを考える
・線分の集合をすべて捜索し、q以上であればtrue, 未満ならfalseとする
・k - 1のときtrue, kのときtrue ならスキップ
・k - 1のときfalse, kのときfalse ならスキップ
・k - 1のときtrue, kのときfalse なら結果配列にk - 1を
・k - 1のときfalse, kのときtrue なら結果配列にkを追加
・n + 1回分行う
・結果配列から2個ずつ取り出す

ただ、これですとn x m x 線分集合分を探索しなくてはならず
n, mが大きくなった時にパフォーマンスが悪そうです。
より良い方針はありますでしょうか。

以下は例です。
領域：(n, m) = (3, 9)
線分の集合
[[0, 0], [0, 3]]
[[0, 8], [0, 9]]
[[0, 1], [4, 1]]
[[6, 1], [7, 1]]
[[1, 3], [3, 3]]

q = 1のとき [0, 4], [6, 9]
q = 2のとき [0, 3]
q = 3のとき [1, 2]

以下はイメージ図です。宜しくお願い致します。

Comments

[swordone]

複数の線分が重なるというケースは考えなくてもよいですか？
例:[[0,0],[0,4]]と[[0,2],[0,6]]

[millionx]

はい、考えなくてもよいです。

[swordone]

例の座標で書いてみましたが、結果の意味が分かりません。
[0,4]は何を意味しているのでしょうか？

[millionx]

すいません、結果の値を間違えておりましたので修正いたしました。
q = 2のとき [0, 4]ではなく[0, 3]でした。
x = 0, 1, 2, 3で線分が2以上交わっているので[0, 3]としております。

q = 1のとき
x = 0, 1, 2, 3, 4
x = 6, 7, 8, 9
で線分が1以上交わっているので[0, 4], [6, 9]としております。

Answer 1

0~nの配列かなにかを用意しておいて、線分のx座標の位置をカウントしていけばいいです。
つまり例だと、要素数10の配列[0,0,0,0,0,0,0,0,0]を用意し、
最初の[0, 0], [3, 0]は0,1,2,3の要素を1増やして[1,1,1,1,0,0,0,0,0]
次の[[0, 8], [0, 9]]は8と9の要素を加算して[1,1,1,1,0,0,0,1,1]
という具合にすべての線分のx座標をチェックします。
完成した配列で、q以上の要素が連続している部分を取り出せばいいです。

Comments

[millionx]

ありがとうございます！