Activity arrangement greedy algorithm visualization

previously on

There are n activities (assuming that n is large and manpower arrangement is difficult)

The start time and end time of n activities are known

But I also want to make full use of resources and arrange the largest number of activities

Greedy Algorithm

Language: python

Third party libraries for visualization: numpy,matplotlib

Start the activity arrangement Tour

Greedy algorithm overview:

Create activity classes (or structures), instantiate them as one activity object according to user input, and add activities according to the end time of the activity
When selecting activities, the earliest end of the activity is selected first, leaving the most time for the rest of the activities to arrange (the most activities may be arranged for the rest of the time each time, or the least time resources occupied by oneself each time), which is called greed.

details

The implementation of the algorithm does not depend on the specific language, but for the convenience of visualization, I failed to block the availability of python
The container for the data selects Python's coolie: list. Sort function is used to sort according to the attribute value of the object, with only one line,
Highlight greedy algorithm
Implementation process: a list of objects arranged by end time. The first activity must be selected to see whether the second activity is
Conflict with the last selected activity (only depending on its start time). Conflict no? Don't choose: choose; then look at the next one, and repeat the process of judging the conflict, that is, OK
For visualization, add an attribute (tag) to the object: select; initialize to false
In the visualization part, draw a ladle according to the gourd, and give the small demo. There is an interface API, and the incoming data is ok

Upper code (python3)

import matplotlib.pyplot as plt

class Activation(object):
    def __init__(self,start,end,id):
        self.start = start
        self.end = end
        self.select = False
        self.id = id

def main():
    act_num = eval(input("Please enter the total number of activities:"))
    act_list = []
    for i in range(act_num):
        a = eval(input("Please input number 1.{}Activity start time:".format(i+1)))
        b = eval(input("Please input number 1.{}Activity end time:".format(i+1)))
        if a>=b:
            print("error:End time less than or equal to start")
            b = eval(input("Please re-enter the{}Activity end time:".format(i+1)))
        act_list.append(Activation(a,b,i+1))
    act_list.sort(key = lambda obj:obj.end,reverse = False)
    last = 0
    for i in range(act_num):
        if i==0:
            act_list[i].select = True
        elif act_list[i].start >= act_list[last].end:
            act_list[i].select = True
            last = i
    #Visualization (results)
    fig, ax = plt.subplots()
    order = 1  #Row number
    for i in act_list:
        if i.select == True:
            ax.broken_barh([(i.start,i.end-i.start)], (10*order,9),facecolor='green')
        else:
            ax.broken_barh([(i.start,i.end-i.start)], (10*order,9),facecolor='blue')
        order = order + 1
    ax.set_ylim(5, 10*act_num+15)
    #Adaptive size
    ax.set_xlim(0, act_list[-1].end)
    ax.set_xlabel('time order')
    act_y = []
    act_lebal = []
    for i in range(act_num):
        act_y.append(10*i+15)
        act_lebal.append("activity{}".format(act_list[i].id))
    ax.set_yticks(act_y)
    ax.set_yticklabels(act_lebal)
    ax.grid(True)
    ax.annotate('race interrupted', (61, 25),
                xytext=(0.8, 0.9), textcoords='axes fraction',
                arrowprops=dict(facecolor='black', shrink=0.05),
                fontsize=16,
                horizontalalignment='right', verticalalignment='top')

    plt.show()

main()

Operation effect:

A small demo of matplotlib

import matplotlib.pyplot as plt

fig, ax = plt.subplots()
ax.broken_barh([(110, 30), (150, 10)], (10, 9), facecolors='blue')
ax.broken_barh([(10, 50), (100, 20), (130, 10)], (20, 9),
               facecolors=('red', 'yellow', 'green'))
ax.set_ylim(5, 35)
ax.set_xlim(0, 200)
ax.set_xlabel('seconds since start')
ax.set_yticks([15, 25])
ax.set_yticklabels(['Bill', 'Jim'])
ax.grid(True)
ax.annotate('race interrupted', (61, 25),
            xytext=(0.8, 0.9), textcoords='axes fraction',
            arrowprops=dict(facecolor='black', shrink=0.05),
            fontsize=16,
            horizontalalignment='right', verticalalignment='top')

plt.show()

Small demo style

Tags: Python REST Attribute less

Posted on Thu, 16 Jan 2020 00:47:43 -0800 by gushy