Python 時刻を比較して一部の時間をくり抜く

Question

Python初心者にお教えください

以下のような時刻のデータがあったときに、Aの時刻からBの時刻をくり抜いた結果Cが欲しいです。

　　　　　　　　　開始　　　　　　　　終了
A ＝［2021/08/23 12：00：00,2021/08/23 18：00：00］
B ＝［2021/08/23 13：00：00,2021/08/23 14：00：00］

C ＝［(2021/08/23 12：00：00,2021/08/23 13：00：00),(2021/08/23 14：00：00,2021/08/23 18：00：00)］

またBの時刻が複数あったときやAの終了をBの終了が上回るときは,以下のような結果が欲しいです

　　　　　　　　　開始　　　　　　　　終了
A ＝［2021/08/23 12：00：00,2021/08/23 18：00：00］
B ＝［(2021/08/23 13：00：00,2021/08/23 14：00：00),(2021/08/23 17：00：00,2021/08/23 21：00：00)］

C ＝［(2021/08/23 12：00：00,2021/08/23 13：00：00),(2021/08/23 14：00：00,2021/08/23 17：00：00)］

Comments

[Ftps]

くり抜くというのは、そのデータの一部を持ってくるということでしょうか？また、Cの順番を教えて下さい(開始、終了など)

[otn]

A[0],A[1],B[0],B[1]の大小を比較して場合分けすれば良いと思いますが、
if文を知らないと言うことなのでしょうか？あるいは大小比較のやり方が分からない？

[udon-ken]

> 以下のような時刻のデータがあったときに
そもそも、それが代入式であるとしたらエラーになって代入もできないです。
単純にやるとしたら""を付けて文字列にするくらいですが、それだと単なる文字列です。
時刻としてなんらかの処理をするなら、まず時刻としてデータを整える必要があります。

つまり、そのような時刻データがありえませんので質問が成り立っていません。

Answer 1

A も B も複数の範囲を指定できるようにしたので、
1つの場合でも ( ) をつけて tuple にしないといけません。
というのが最初のコードでしたが、その問題を修正しました。

def range_sub(a, b):
	if len(a) == 0 or len(b) == 0: return []
	if type(a[0]) != tuple: a = [tuple(a)]
	if type(b[0]) != tuple: b = [tuple(b)]
	c = []
	for t in a:
		c.append([t[0], 2])
		c.append([t[1], 3])
	for t in b:
		c.append([t[0], 1])
		c.append([t[1], 4])
	c.sort();
	aa = bb = False
	d = []
	for t in c:
		if t[1] == 2:
			if not aa and not bb: d.append(t[0])
			aa = True
		elif t[1] == 3:
			if aa and not bb: d.append(t[0])
			aa = False
		elif t[1] == 1:
			if not bb and aa: d.append(t[0])
			bb = True
		else:
			if bb and aa: d.append(t[0])
			bb = False
	c = []
	for i in range(0, len(d), 2):
		c.append((d[i], d[i+1]))
	if len(c) == 1: c = [c[0][0], c[0][1]]
	return c


a = ["2021/08/23 12:00:00", "2021/08/23 18:00:00"]
b = ["2021/08/23 13:00:00", "2021/08/23 14:00:00"]
c = range_sub(a, b)
print(a)
print(b)
print(c)
print()

a = ["2021/08/23 12:00:00", "2021/08/23 18:00:00"]
b = [("2021/08/23 13:00:00", "2021/08/23 14:00:00"), ("2021/08/23 17:00:00", "2021/08/23 21:00:00")]
c = range_sub(a, b)
print(a)
print(b)
print(c)
print()

a = ["2021/08/23 12:00:00", "2021/08/23 18:00:00"]
b = ["2021/08/23 19:00:00", "2021/08/23 20:00:00"]
c = range_sub(a, b)
print(a)
print(b)
print(c)

わからないことがあれば、コメントをください。

Answer 2

Subtract Overlaps Between Two Ranges Without Setsが参考になりそうです。
こういった問題はSegment treeを使うとよいようです。

以下は上記の[回答コード]((https://stackoverflow.com/a/6462731)を修正して試してみた例です。
正直アルゴリズムは理解できていませんが、質問例ではうまく計算できました。
なお、実際の利用には日時のデータを整数値に変換してください（難しくはありません）。

参考：セグメント木を徹底解説！0から遅延評価やモノイドまで

from functools import reduce

# Subtract Overlaps Between Two Ranges Without Sets
# https://stackoverflow.com/questions/6462272/subtract-overlaps-between-two-ranges-without-sets
# https://stackoverflow.com/a/6462731
class IntervalTree:
    def __init__(self, h, left, right):
        self.h = h
        self.left = left
        self.right = right

def merge(A, B, op, l=-float("inf"), u=float("inf")):
    if l > u:
        return None
    if not isinstance(A, IntervalTree):
        if isinstance(B, IntervalTree):
            opT = op
            A, B, op = B, A, (lambda x, y : opT(y,x))
        else:
            return op(A, B)
    left = merge(A.left, B, op, l, min(A.h, u))
    right = merge(A.right, B, op, max(A.h, l), u)
    if left is None:
        return right
    elif right is None or left == right:
        return left
    return IntervalTree(A.h, left, right)

def to_range_list(T, l=-float("inf"), u=float("inf")):
    if isinstance(T, IntervalTree):
        return to_range_list(T.left, l, T.h) + to_range_list(T.right, T.h, u)
    #return [(l, u-1)] if T else [] # -
    return [(l, u)] if T else []    # +

def range_list_to_tree(L):
    return reduce(lambda x, y : merge(x, y, lambda a, b: a or b), 
        #[ IntervalTree(R[0], False, IntervalTree(R[1]+1, True, False)) for R in L ]) # -
        [ IntervalTree(R[0], False, IntervalTree(R[1], True, False)) for R in L ])    # +

# helper function
def get_interval_list( A, B):
    r1 = range_list_to_tree(A)
    r2 = range_list_to_tree(B)
    diff = merge(r1, r2, lambda a, b : a and not b)
    return to_range_list(diff)

A =[(12, 18)]
B =[(13, 14)]
ret = get_interval_list( A, B)
print(ret) # [(12, 13), (14, 18)]

A = [(12, 18)]
B = [(13, 14), (17, 21)]
ret = get_interval_list( A, B)
print(ret) # [(12, 13), (14, 17)]