greedy

package
v0.0.0-...-7dccd96 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 23, 2016 License: MIT Imports: 2 Imported by: 0

Documentation

Overview

Package greedy implements solutions for the problems described in the sub-chapter Greedy Algorithms of chapter Greedy Algorithms and Invariants of the book Elements of Programming Interview.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func HuffmanEncoding 

func HuffmanEncoding(symbols []*Symbol)

HuffmanEncoding assigns huffman code to given symbols based on its given frequency. The time complexity is O(n*log(n))), and O(n) additional space is needed.

func MinWaitingTime 

func MinWaitingTime(times []int) (waiting int)

MinWaitingTime returns a time that represents a sum of all the minimum waiting times ordered in a way in which to process queries minimizes time.

func PairTasks 

func PairTasks(tasks []int) (pairs [][]int)

PairTasks compute an optimum set of pairs from given tasks duration such that the maximum pair sum is minimum. The time complexity is O(n*log(n)). Beyond the space needed to write the final result, O(1) additional space is needed.

Types

type Symbol 

type Symbol struct {
	// contains filtered or unexported fields
}

Symbol represents a character with its frequency and optimal binary code.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.