如何可视化基于贪心算法的制造测试调度代码执行过程？

First, we need to accurately track the start and end times for both manufacturing and testing phases of each item, including idle periods in the testing queue. Then we can generate both a detailed interval breakdown and a visual ASCII timeline.

Complete Code #

# Parse input data
input_lines = [
    "1 / 5 / 7",
    "2 / 1 / 2",
    "3 / 8 / 2",
    "4 / 5 / 4",
    "5 / 3 / 7",
    "6 / 4 / 4"
]

data = []
for line in input_lines:
    parts = line.split('/')
    item_id = int(parts[0].strip())
    m_i = int(parts[1].strip())
    t_i = int(parts[2].strip())
    data.append([item_id, m_i, t_i])

# Sort items by manufacturing time (greedy approach)
data.sort(key=lambda x: x[1])
print(f"Production order: {', '.join(str(x[0]) for x in data)}")

# Calculate start/end times for manufacturing and testing
schedule_data = []
prev_man_end = 0
prev_test_end = 0

for item in data:
    item_id, m_i, t_i = item
    # Manufacturing starts right after previous item finishes
    man_start = prev_man_end
    man_end = man_start + m_i
    # Testing starts when manufacturing finishes OR previous test finishes, whichever is later
    test_start = max(man_end, prev_test_end)
    test_end = test_start + t_i
    
    schedule_data.append({
        'id': item_id,
        'man_start': man_start,
        'man_end': man_end,
        'test_start': test_start,
        'test_end': test_end
    })
    
    prev_man_end = man_end
    prev_test_end = test_end

total_time = prev_test_end
print(f"Total production time: {total_time}\n")

# Generate visual timeline with time labels
time_labels = [str(t).rjust(2) for t in range(total_time)]

# Initialize bars: Manufacturing starts empty, Testing starts as idle ('I')
man_bar = [' '] * total_time
test_bar = ['I'] * total_time

# Populate manufacturing bar with item IDs
for entry in schedule_data:
    for t in range(entry['man_start'], entry['man_end']):
        man_bar[t] = str(entry['id'])

# Populate testing bar with item IDs (overwriting idle markers)
for entry in schedule_data:
    for t in range(entry['test_start'], entry['test_end']):
        test_bar[t] = str(entry['id'])

# Print the visual timeline
print("Visual Schedule Timeline:")
print("Time: " + ' '.join(time_labels))
print("Man:  " + ' '.join(man_bar))
print("Test: " + ' '.join(test_bar))

# Print detailed interval breakdown for clarity
print("\nDetailed Interval Breakdown:")
print("Manufacturing:")
for entry in schedule_data:
    print(f"  Item {entry['id']}: Starts at {entry['man_start']}, Ends at {entry['man_end']}")

print("\nTesting (including idle periods):")
current_time = 0
for entry in schedule_data:
    if current_time < entry['test_start']:
        print(f"  Idle: Starts at {current_time}, Ends at {entry['test_start']}")
    print(f"  Item {entry['id']}: Starts at {entry['test_start']}, Ends at {entry['test_end']}")
    current_time = entry['test_end']

Sample Output #

Production order: 2, 5, 6, 1, 4, 3
Total production time: 28

Visual Schedule Timeline:
Time: 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
Man:  2  2  5  5  5  6  6  6  6  1  1  1  1  1  4  4  4  4  4  3  3  3  3  3  3  3  3  3
Test: I  2  2  I  5  5  5  5  5  5  5  6  6  6  6  1  1  1  1  1  1  1  4  4  4  4  3  3

Detailed Interval Breakdown:
Manufacturing:
  Item 2: Starts at 0, Ends at 1
  Item 5: Starts at 1, Ends at 4
  Item 6: Starts at 4, Ends at 8
  Item 1: Starts at 8, Ends at 13
  Item 4: Starts at 13, Ends at 18
  Item 3: Starts at 18, Ends at 26

Testing (including idle periods):
  Idle: Starts at 0, Ends at 1
  Item 2: Starts at 1, Ends at 3
  Idle: Starts at 3, Ends at 4
  Item 5: Starts at 4, Ends at 11
  Item 6: Starts at 11, Ends at 15
  Item 1: Starts at 15, Ends at 22
  Item 4: Starts at 22, Ends at 26
  Item 3: Starts at 26, Ends at 28

Key Notes #

• The code first parses and sorts the items by manufacturing time (your original greedy approach).
• It calculates exact start/end times for each phase:
  • Manufacturing runs sequentially with no idle time.
  • Testing starts only when both the item is manufactured and the testing queue is free.
• The visual timeline uses a grid format where each column represents a time unit:
  • Man row shows which item is being manufactured at each time.
  • Test row shows either the item being tested or I for idle.
• The detailed breakdown lists all intervals, including idle periods in the testing queue for full transparency.

内容的提问来源于stack exchange，提问作者Suzuna Minami